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
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:
and adding 1
but since 2 and 5 are coprime, this is equivalent to the two conditions
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
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
Clearly, 2^{t-3} and 5^{t-1} are coprime, then by the Chinese Remainder Theorem, there is a k such that
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:
and
Together, these result in
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
Then H is generated multiplicatively by 71, that is
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
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
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
but then, using that 9*7=63=64-1 \equiv -1 \text{ mod }16 we obtain
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:
Then
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.
1475.pdf (1.44 MB)
