Squares Ending in n Occurrences of m-Digit Pattern

== Theorem ==
Suppose there exists some integer $x$ such that $x^2$ ends in some $m$-digit pattern ending in an odd number not equal to $5$ and is preceded by another odd number, i.e.:
:$\exists x \in \Z: x^2 \equiv \sqbrk {1 a_1 a_2 \cdots a_m} \pmod {2 \times 10^m}$
where $a_m$ is odd, $a_m \ne 5$ and $m \ge 1$.
Then for any $n \ge 1$, there exists some integer with not more than $m n$-digits such that its square ends in $n$ occurrences of the $m$-digit pattern.
=== Corollary ===
If such a pattern ends in an even number, one must divide the pattern by $4$ until it becomes an odd number (keeping every leading zero), and check if the above condition is satisfied.
If it is, there is a number less than $4^s 10^{m n}$ with its square ending in $n$ occurrences of the $m$-digit pattern.
== Proof ==
We prove that there exists a sequence $\sequence {b_n}$ with the properties:
:$b_n < 10^{m n}$
:$b_n^2 \equiv \underbrace {\sqbrk {1 \paren {a_1 \cdots a_m} \cdots \paren {a_1 \cdots a_m}}}_{n \text { occurrences}} \pmod {2 \times 10^{m n}}$
by induction:
=== Basis for the Induction ===
For $n = 1$, we choose the number $b_1 = x \pmod {10^m}$ with $b_1 < 10^m$.
Note that:
This is the basis for the induction.
=== Induction Hypothesis ===
This is our induction hypothesis:
:There exists some $b_r$ such that:
::$b_r < 10^{m r}$
::$b_r^2 \equiv \underbrace {\sqbrk {1 \paren {a_1 \cdots a_m} \cdots \paren {a_1 \cdots a_m}}}_{r \text { occurrences}} \pmod {2 \times 10^{m r}}$
Now we need to show true for $n = r + 1$:
:There exists some $b_{r + 1}$ such that:
::$b_{r + 1} < 10^{m \paren {r + 1} }$
::$b_{r + 1}^2 \equiv \underbrace {\sqbrk {1 \paren {a_1 \cdots a_m} \cdots \paren {a_1 \cdots a_m}}}_{r + 1 \text { occurrences}} \pmod {2 \times 10^{m \paren {r + 1}}}$
=== Induction Step ===
This is our induction step:
Let $b < 10^m$ and $b_{r + 1} = b \times 10^{m r} + b_r$.
Note that:
The rightmost $m r$ digits already satisfy the condition, so we consider the next $m + 1$ digits.
We want:
:$2 b b_r + 1 + 2 k \equiv \sqbrk {1 a_1 \cdots a_m} \pmod {2 \times 10^m}$
We first take Modulo $10^m$:
:$2 b b_r + 1 + 2 k \equiv \sqbrk {a_1 \cdots a_m} \pmod {10^m}$
So we need to solve:
:$b b_r + t \times 10^m = \dfrac {\sqbrk {a_1 \cdots a_m} - 1} 2 - k$
for integer solutions $b, t$.
Since $a_m \ne 5$ and is odd:
:$2, 5 \nmid b_r$
so $b_r$ and $10^m$ are coprime.
By Bézout's Identity, a solution for $b, t$ exists.
We can also find a solution with $0 \le b < 10^m$.
For this $b$, if;
:$2 b b_r + 1 + 2 k \equiv \sqbrk {1 a_1 \cdots a_m} \pmod {2 \times 10^m}$
then take $b' = b$, $b_{r + 1} = b' \times 10^{m r} + b_r$ and we are done.
It may happen that:
:$2 b b_r + 1 + 2 k \equiv \sqbrk {0 a_1 \cdots a_m} \pmod {2 \times 10^m}$
In this case, take $b' = b \pm 5 \times 10^{m - 1}$, whichever is between $0$ and $10^m$.
We have:
hence $b_{r + 1} = b' \times 10^{m r} + b_r$ satisfy our conditions as well.
By the Principle of Mathematical Induction, the sequence $\sequence {b_n}$ exists.
== Example ==
== Also see ==
* Squares Ending in 5 Occurrences of 2-Digit Pattern
Since:
it is seen that all the numbers in that page satisfy the condition above.
Hence there are squares with any number of occurrences of these patterns.
Category:Number Theory
Category:Recreational Mathematics
Category:Squares Ending in n Occurrences of m-Digit Pattern