Which is the least natural $n$ such that there is a power of $n$ whose last $t \geq 4$ digits are all 1?

Spoiler alert, it's 71.

In this discussion I'll prove this fact, use Mathematica to guide the proof, and find explicit values of the numbers that appear throughout the proof. I assume knowledge of Modular Arithmetic in this discussion.

The last $t$ digits of a number are its remainder after division by $10 ^{t}$, so we are searching for an $n$ and a $k$ such that $$ n^k \equiv 1...1 \text{ mod }10^{t} $$ where the low dots mean the 1's are repeated $t$ times. Since 9 and 10 are coprime, we can multiply both sides by 9 and get the equivalent condition: $$9n^k \equiv 9...9 \text{ mod }10^{t}$$ and adding 1 $$9n^k+1\equiv 10^{t}\equiv 0 \text{ mod } 10^{t}$$ but since 2 and 5 are coprime, this is equivalent to the two conditions

$$9n^k+1\equiv 0 \text{ mod } 2^{t}$$ $$9n^k+1\equiv 0 \text{ mod } 5^{t}$$

Part one: Showing that 71 satisfies the property

71 might seem as an arbitrary number to chose for this problem, but it has two important characteristics which will be proved below:

Lemma 1: Modulo $2^t$, $71$ generates (multiplicatively) all numbers whose remainder modulo $16$ is either $1$ or $7$. This needs proving that $ord_{2^t}71=2^{t-3}$.

Lemma 2: Modulo $5^t$, $71$ generates (multiplicatively) all numbers whose remainder modulo 5 is 1. This needs proving that $ord_{5^t}71=5^{t-1}$

We have that $1...1 \text{ mod }16 = 7 \text{ mod }16$, since $10000$ is a multiple of $2^4=16$, (here one can notice that it is important that $t \geq 4)$, and $1111=16*69+7$. Furthermore $1...1 \text{ mod }5 =1 \text{ mod } 5$, since $10$ is a multiple of $5$.

Combining these results with Lemmata 1 and 2, this means that there are $k_1,k_2$ such that $$71^{k_1} \equiv 1...1 \text{ mod } 2^t$$ $$71^{k_2} \equiv 1...1 \text{ mod } 5^t$$

Since we know $k_1$ and $k_2$ must exist, we can now try to find them with Mathematica. FindInstance helps with this:

k1[t_] := 
 Module[
{modulus = 2^t, ones = Mod[FromDigits@Table[1, t], 2^t]}, 
First@Values@Flatten@
FindInstance[Mod[71^x, modulus] == ones && x > 0, {x}, Integers]
]

k2[t_] :=
Module[
{modulus = 5^t, ones = Mod[FromDigits@Table[1, t], 5^t]}, 
First@Values@Flatten@
FindInstance[Mod[71^x, modulus] == ones && x > 0, {x}, Integers]
]

The proofs of the Lemmata will give us upper bounds for the values of $k_1$ and $k_2$, so we can be sure this computation will finish.

Let's see some results:

 Table[k1[t], {t, 4, 15}]

gives

 {1, 1, 1, 1, 17, 49, 113, 113, 113, 625, 1649, 1649}

and

 Table[k2[t], {t, 4, 15}]

gives

{13, 263, 263, 6513, 37763, 115888, 115888, 4022138, 13787763,13787763, 13787763, 1234490888}

A simple check with

And @@ 
    Table[  
      PowerMod[71, k1[t], 2^t] == Mod[FromDigits@Table[1, t], 2^t] &&
      PowerMod[71, k2[t], 5^t] == Mod[FromDigits@Table[1, t], 5^t] , 
    {t, 4, 10}]

gives True.

It is known that working with PowerMod is faster, yet it FindInstance fails to work with it. Trying to execute the following code will give an error:

 Module[{t = 14, modulus, ones},
 modulus = 5^t; 
 ones = Mod[FromDigits@Table[1, t], 5^t]; 
     FindInstance[PowerMod[71, x, modulus] == ones && x > 0, {x}, Integers]
     ]

The error message is The methods available to FindInstance are insufficient to find the requested instances or prove they do not exist.

However, a simple loop should also make the work, for example, lets define

kk2[t_]:=
Module[
{modulus, ones, res = 1},
modulus = 5^t; 
ones = Mod[FromDigits@Table[1, t], 5^t]; 
While[ PowerMod[71, res, modulus] != ones, res++];
res
]

This just iterates until getting to the required number. Of course, we get the same results

Table[kk2[t],{t,4,15}]

gives

  {13, 263, 263, 6513, 37763, 115888, 115888, 4022138, 13787763, 13787763, 13787763, 1234490888}

Nevertheless, this method is way slower that the original one. We check this with AbsoluteTiming:

Table[First@AbsoluteTiming[k2[t]], {t, 4, 15}]

gives

{0.006079, 0.00533, 0.00528, 0.005771, 0.008156, 0.014349, 0.014382, 0.315804, 1.0729, 1.06104, 1.05002, 93.0594}

and

Table[First@AbsoluteTiming[kk2[t]], {t, 4, 15}]

gives

{0.000034, 0.000144, 0.000137, 0.003661, 0.022389, 0.071185, 0.071812, 2.72244, 9.51421, 9.45131, 10.3856, 1183.75}

In particular, the last computation took me around 20 minutes.

Now, let's continue with the exercise.

We know there are $k_1,k_2$ such that $$71^{k_1} \equiv 1...1 \text{ mod } 2^t$$ $$71^{k_2} \equiv 1...1 \text{ mod } 5^t$$

Clearly, $2^{t-3}$ and $5^{t-1}$ are coprime, then by the Chinese Remainder Theorem, there is a $k$ such that $$k\equiv k_1 \text{ mod }2^{t-3}$$ $$k\equiv k_2 \text{ mod } 5^{t-1}$$ that implies that $o_1 := ord_{2^t}71=2 ^{t-3}$ divides $k-k_1$ and $o_2:=ord_{5^t}71=5^{t-1}$ divides $k-k_2$.

Now if we calculate $71^k$:

$$71^k \text{ mod }2^t \equiv 71^{k-k_1}71^{k_1} \text{ mod }2^t \equiv 71^{o_1 *(k-k_1)/o_1}71^{k_1}\text{ mod }2^t $$ $$ \equiv 1*71^{k_1}\text{ mod }2^t \equiv 1...1 \text{ mod }2^t$$ and $$71^k \text{ mod }5^t \equiv 71^{k-k_2}71^{k_2} \text{ mod }5^t \equiv 71^{o_2 *(k-k_2)/o_2}71^{k_2}\text{ mod }5^t $$ $$ \equiv 1*71^{k_2}\text{ mod }5^t \equiv 1...1 \text{ mod }5^t$$

Together, these result in $$71^k \equiv 1...1 \text{ mod }10^t$$

We can use ChineseRemainder to obtain $k$:

k[t_] := ChineseRemainder[{k1[t], k2[t]}, {2^(t - 3), 5^(t - 1)}]

Thus

Table[k[t], {t, 4, 10}]

gives

{13, 1513, 6513, 6513, 506513, 13006513, 88006513}

Now comes the final and most important part of the exercise: checking.

Table[PowerMod[71, k[t], 10^(t)], {t, 4, 15}]

gives

{1111, 11111, 111111, 1111111, 11111111, 111111111, 1111111111, 11111111111, 111111111111, 1111111111111, 1111111111111, 111111111111111}

which supports the correctness of the results. Note that by the implementation of FindInstance and ChineseRemainder this $k$ will be the least one that satisfies this property.

Part two: Proofs of the Lemmata

This section is optional, as it is more theoretical than computational.

Proof of Lemma 1

Lemma 1 says that, with $$H := \{x\in (\mathbb{Z}/2^t)^* \text{ such that } x\equiv 1 \text{ mod }16 \text{ or } x\equiv 7 \text{ mod }16 \}$$ Then $H$ is generated multiplicatively by $71$, that is $$ H= \{71^s \text{ mod } 2^t , s\in \mathbb{N}\}$$ Now, since $(7 \text{ mod }16) * (7 \text{ mod }16) \equiv 49 \text{ mod }16 \equiv 1 \text{ mod }16$, we have that $H$ is a multiplicative group, and since $71 = 64+7 \equiv 7 \text{ mod }16$ we have that $71\in H$, so the set of powers of 71 Modulo $2^t$ is contained in $H$.

Now let's count all the possible elements of $H$:

The elements that are 1 Modulo 16 are of the form $16r+1$, with $r$ starting from 0, and up to an $r_{max}$ such that $16 r_{max}+1$ is the last number $1 \text{ mod }16$ smaller than $2^t$, because if we go further than $2^t$, the elements will repeat. Or, more mathematically said, we are only counting the equivalence classes Modulo 16 by their representatives that are greater than $0$ and less than $2^t$.

Since $t\geq 4$ (!), $2^t \equiv 0 \text{ mod }16$, the last number $1 \text{ mod } 16$ before $2^t$ is $(2^t-16)+1$, with gives $r_{max}=2^{t-4}-1$. With $r\in \{0,..., 2^{t-4}-1\}$ we have that there are $2^{t-4}$ elements $1 \text{ mod } 16$ in $H$. The count for the numbers $7 \text{ mod } 16$ is the same, mutatis mutandis (1 by 7), and also gives $2^{t-4}$.

So $H$ has $2^{t-4}+2^{t-4}=2^{t-3}$ elements.

Now we must prove that the powers of $71$ give $2^{t-3}$ different possibilities, and so they will cover the whole group $H$, that is $ord_{2^t} 71 =2^{t-3}$.

This will be a consequence of the following result, which we will prove by induction:

The greatest power of two that divides $71^{2^{t-3}}-1$ is $2^t$. Or, equivalently, $71^{2^{t-3}}$ is of the form $2^{t} l+1$, where $2$ does not divide $l$.

For $t=4$, $71^2-1 = 5040=16*315$. If the result holds for $t\geq4$, then $71^{2^{t-3}}=2^t l+1$, where $2$ does not divide $l$. Then $71^{2^{t-2}}$ $=(2^t l+1)^{2}$ $=2^{2t} l^2+2^{t+1}l+1$ $=2^{t+1}(2^{t-1}l^2+l)+1$ and since $2$ does not divide $l$, it does not divide $2^{t-1}l^2+l$. Thus, the result holds for $t+1$.

This result gives us that $71^{2^{t-3}}\equiv 1 \text{ mod } 2^t$, so that if $o=ord_{2^t}71$, then $o$ divides $2^{t-3}$. That means $o$ is a power of two, $o=2^s, \ s\leq t-3$. On the other hand, by the definition of order we have $71^o=71^{2^{s}}\equiv 1 \text{ mod } 2^t$, which gives that $2^t$ divides $71^{2^s}-1$. But the past result says that the greatest power of $2$ dividing $71^{2^s}-1$ is $2^{s+3}$, and thus $t\leq s+3$. Combining this, we have $s=t-3$, and finally $ord_{2^t}71=2^{t-3}$.

Proof of Lemma 2

The proof of Lemma 2 if fairly similar to the one of Lemma 1, though with some caveats.

Now we have $$H:=\{x\in (\mathbb{Z}/5^t)^* \text{ such that } x\equiv 1 \text{ mod }5 \}$$

The elements of $H$ are now of the form $5r+1$, up to $5^t-5+1$, which results in $H$ having $5^{t-1}$ different elements, so we need to prove that $ord_{5^t}71=5^{t-1}$.

By induction, we prove that $5^t$ is the greatest power of $5$ that divides $71^{5^{t-1}}-1$, for all $t\geq 1$ (for this part we do not need $t\geq 4$). For $t=1$, $71^1-1=70=5*14$. If for some $t$ we have that $71^{5^{t-1}}=5^tl+1$ where $5$ does not divide $l$, then $71^{5^t}$ $=(5^tl+1)^5$ $=5^{t+1}l'+1$, where $l'=5^{4t-1}l^5+5^{3t}l^4+2*3^{2t}l^3+2*5^t+l$. Since $5$ does not divide $l$, it does not divide $l'$.

By the same argument as in Lemma 1, $ord_{5^t}71=5^{t-1}$.

Note that these two results imply that $k_1(t)\leq 2^{t-3}$ and $k_2(t)\leq 5^{t-1}$.

Part three: Showing that 71 is the least number with this property

This part requires knowledge of the Legendre Symbol.

Given $t\geq 4$, say we have and $n$ satisfying the property. that is, there is a $k$ such that the last $t$ digits of $n^k$ are all ones. As in the first part, this is equivalent to $$9n^k+1\equiv 0 \text{ mod } 2^{t}$$ $$9n^k+1\equiv 0 \text{ mod } 5^{t}$$

Modulo $8$, all squares are either $0,1,4 \text{ mod }8$:

Mod[Range[8]^2, 8]

gives

{1, 4, 1, 0, 1, 4, 1, 0}

So, since $t\geq 4\geq 3$, and $2^t$ divides $9n^k+1$, then $8$ divides $9n^k+1$. If $k$ were even, then $9n^k$ would be a perfect square, and $9n^k+1$ would be either $1,2,5 \text{ mod } 8$, which is a contradiction. Thus $k$ is odd, let $k=2l+1$. Now we have, since $t\geq4$, that $16$ divivdes $9n^k+1$, that is $$9n^{2l+1}+1\equiv 0 \text{ mod 16}$$ but then, using that $9*7=63=64-1 \equiv -1 \text{ mod }16 $ we obtain $$n^{2l}*n\equiv 7 \text{ mod } 16$$ Modulo 16, the squares are:

Mod[Range[16]^2,16]

which results in

{1, 4, 9, 0, 9, 4, 1, 0, 1, 4, 9, 0, 9, 4, 1, 0}

It can be proven, on a case by case basis, that $n$ must be $7 \text{ mod } 16$:

First, if $l=0$, we are done, so from now on we can consider $l\geq1$.

Second, if $n^2\equiv 0 \text{ mod }16$, this gives a contradiction.

Third, if $n^2 \equiv 1 \text{ mod } 16$, we are done.

Fourth, if $n^2 \equiv 4\text{ mod }16$, then $ 4^l n \equiv 7 \text{ mod }16 $, multiplying by $4$ and using $l\geq1$ we get $0\text{ mod }16 \equiv 16*4^{l-1}n \text{ mod }16 \equiv 4*7 \text{ mod }16 \equiv 28\text{ mod }16\equiv 12 \text{ mod 16}$, which is a contradiction.

Fifth, if $n^2\equiv 9 \text{ mod }16$, then $9^l n\equiv 7 \text{ mod }16$. If $l$ is even, since $81\equiv 1 \text{ mod }16$, we are done. If $l$ is odd, $9^l \equiv 9 \text{ mod } 16$, so $9n \equiv 7 \text{ mod }16$, and multiplying by $9$ we get $n\equiv 81 n \text{ mod }16 \equiv 9*7 \text{ mod }16 \equiv 63 \text{ mod }16\equiv -1 \text{ mod }16 $. But then, $n^{2l+1}\equiv (-1)^{2l+1}\text{ mod }16\equiv -1 \text{ mod} 16 \equiv 15 \text{ mod } 16$, which is a contradiction.

So, our first result is that $k$ is odd and $n\equiv 7 \text{ mod }16 $.

Now, since $t\geq 4\geq 1$ and $9n^k+1\equiv 0 \text{ mod }5^t$, we have that $5$ divides $9n^k+1$, that is $9n^k\equiv -1 \text{ mod }5$. Because of this, $5$ does not divide $n$, and thus, the Legendre symbol of $n$ modulo $5$ is well defined. Since $k$ is odd, $9n^{k+1}$ is a perfect square, so it's Legendre symbol modulo $5$ is $1$: $$\left(\frac{9n^{k+1}}{5}\right)=1$$ Then $$1=\left(\frac{9n^{k+1}}{5}\right)=\left(\frac{9n^{k}}{5}\right)\left(\frac{n}{5}\right)=\left(\frac{-1}{5}\right)\left(\frac{n}{5}\right)=(-1)^{(5-1)/2}\left(\frac{n}{5}\right)=\left(\frac{n}{5}\right)$$

So, $n$ is a quadratic residue modulo 5, that is, there is an $x$ such that $n\equiv x^2 \text{ mod }5$. Calculating the squares modulo 5:

Mod[Range[5]^2, 5]

gives

 {1, 4, 4, 1, 0}

We know that $n\not\equiv 0 \text{ mod }5$. If $n\equiv 4 \text{ mod }5 \equiv -1\text{ mod }5$, with k odd we have $9n^k \equiv 9*(-1)^k \text{ mod }5 \equiv -9 \text{ mod }5 \equiv 1 \text{ mod } 5 $, which is a contradiction.

So, our second result is that $n\equiv 1 \text{ mod }5$.

The least $n$ that satisfies $n \equiv 7 \text{ mod }16$ and $n\equiv 1 \text{ mod }5$, considering that $5$ and $16$ are coprime, is given by

ChineseRemainder[{7, 1}, {16, 5}]

which results in

71

Since we have proven that $71$ satisfies the property and that any number satisfying it must be greater than or equal to $71$, this finishes the exercise.

Acknowledgement

This exercise is a generalization of the question and methods found on page 59 of the attached PDF (in Portuguese), from the Brazilian Mathematical Society.

Attachments:

1475.pdf