Squares Ending in n Occurrences of m-Digit Pattern

From ProofWiki
Jump to navigation Jump to search

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:

\(\ds b_1^2\) \(=\) \(\ds \paren {x - k \times 10^m}^2\) for some $k \in \Z$
\(\ds \) \(=\) \(\ds k^2 \times 10^{2 m} - 2 x k \times 10^m + x^2\) Square of Sum
\(\ds \) \(\equiv\) \(\ds x^2\) \(\ds \pmod {2 \times 10^m}\)
\(\ds \) \(\equiv\) \(\ds \sqbrk {1 a_1 a_2 \cdots a_m}\) \(\ds \pmod {2 \times 10^m}\) by assumption

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:

\(\ds b_{r + 1}^2\) \(=\) \(\ds \paren {b \times 10^{m r} + b_r}^2\)
\(\ds \) \(=\) \(\ds b^2 \times 10^{2 m r} + 2 b b_r \times 10^{m r} + b_r^2\) Square of Sum
\(\ds \) \(\equiv\) \(\ds 2 b b_r \times 10^{m r} + \underbrace {\sqbrk {1 \paren {a_1 \cdots a_m} \cdots \paren {a_1 \cdots a_m} } }_{r \text { occurrences} } + 2 k \times 10^{m r}\) \(\ds \pmod {2 \times 10^{m \paren {r + 1} } }\) Induction Hypothesis; for some $k \in \Z$

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:

\(\ds 2b' b_r + 1 + 2 k\) \(=\) \(\ds 2 b_r \paren {b \pm 5 \times 10^{m - 1} } + 2 k + 1\)
\(\ds \) \(=\) \(\ds 2 b_r b + 2 k + 1 \pm 10^m\)
\(\ds \) \(=\) \(\ds \equiv \sqbrk {0 a_1 \cdots a_m} \pm 10^m\) \(\ds \pmod {2 \times 10^m}\)
\(\ds \) \(=\) \(\ds \equiv \sqbrk {1 a_1 \cdots a_m}\) \(\ds \pmod {2 \times 10^m}\)

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.

$\blacksquare$


Example

The $n$th term in the sequence:

$611, 734 \, 611, 494 \, 734 \, 611, 63 \, 494 \, 734 \, 611, \dots$

have squares ending in $n$ occurrences of $321$:

\(\ds 373 \, \mathbf {321}\) \(=\) \(\ds 611^2\)
\(\ds 539 \, 653 \, \mathbf {321 \, 321}\) \(=\) \(\ds 734 \, 611^2\)
\(\ds 244 \, 762 \, 335 \, \mathbf {321 \, 321 \, 321}\) \(=\) \(\ds 494 \, 734 \, 611^2\)
\(\ds 4 \, 031 \, 581 \, 323 \, \mathbf {321 \, 321 \, 321 \, 321}\) \(=\) \(\ds 63 \, 494 \, 734 \, 611^2\)


Also see

Since:

\(\ds 11^2\) \(=\) \(\ds 1 \mathbf {21}\)
\(\ds 23^2\) \(=\) \(\ds 5 \mathbf {29}\)
\(\ds 19^2\) \(=\) \(\ds 3 \mathbf {61}\)
\(\ds 13^2\) \(=\) \(\ds 1 \mathbf {69}\)
\(\ds \frac {84} 4\) \(=\) \(\ds 21\)

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.

Retrieved from "https://proofwiki.org/w/index.php?title=Squares_Ending_in_n_Occurrences_of_m-Digit_Pattern&oldid=591667"