Message Boards Message Boards

Powers of 71, an explicit exercise in number theory

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:
6 Replies

Thanks for that information Luis! Very well said.

enter image description here - Congratulations! This post is now featured in our Staff Pick column as distinguished by a badge on your profile of a Featured Contributor! Thank you, keep it coming, and consider contributing your work to the The Notebook Archive!

POSTED BY: EDITORIAL BOARD
Posted 5 years ago

You can speed up a simple loop by knowing that in going from t to t+1, you will need to increase k by a multiple of the MultiplicativeOrder[71,10^t], since we can't destroy the ones we've already established mod 10^t.

MultiplicativeOrder[71,10^4]

is 250. So having found k[4] = 13, you can find k[5]=1513 in 7 tries.

MultiplicativeOrder[71,10^5]`

is 2500, so you can get k[6] in 3 tries.`

POSTED BY: William Isaacs
Posted 5 years ago

Hi Luis Antonio,

Thanks again for the demonstration, I have plenty to learn going back over your very educational post.

I did timing on my idea of using MultiplicativeOrder[]:

k[4] = 13;
k[t_] := k[t] = Module[ 
  {kt,dk,ones}, 
  kt = k[t-1]; 
  dk = MultiplicativeOrder[71,10^(t-1)]; 
  ones = Mod[FromDigits@Table[1, t], 10^t]; 
  While[ 
    PowerMod[71,kt,10^t] != ones, 
    kt = kt + dk ]; 
  kt] 

Table[ AbsoluteTiming[ {t,k[t]}], {t,5,25}  ] // TableForm                                                                                                                                                                                                  

                                5
                    0.0001288   1513

                                6
                    0.0000481   6513

                                7
                    0.0000392   6513

                                8
                    0.0000406   506513

                                9
                    0.000052    13006513

                                10
                    0.0000527   88006513

                                11
                    0.0000519   1088006513

                                12
                    0.0000556   13588006513

                                13
                    0.0000601   163588006513

                                14
                    0.0000802   1413588006513

                                15
                    0.0000764   16413588006513

                                16
                    0.0000524   41413588006513

                                17
                    0.0000484   41413588006513

                                18
                    0.0000656   10041413588006513

                                19
                    0.0023701   160041413588006513

                                20
                    0.0011663   1410041413588006513

                                21
                    0.000427    8910041413588006513

                                22
                    0.0002221   8910041413588006513

                                23
                    0.0007679   2258910041413588006513

                                24
                    0.0005138   14758910041413588006513

                                25
                    0.0007589   239758910041413588006513

The limiting resource in this approach is going to be the MultiplicativeOrder[] call. But even then it looks like you can get k[t] for t in the thousands in reasonable time.

First@AbsoluteTiming[ MultiplicativeOrder[71, 10^5000 ] ]                                                     
2.41778

This order calculation is efficient only because the modulus is easily factored.

POSTED BY: William Isaacs

Thank you for your comments William.

Yours is a good idea, I ran it and it is extremely fast in comparison! The first time I encountered this problem was for $t=2019$, and since my implementation takes a lot of time, specially for the computation of $k_2$, I could only get to $t=20$. With your idea of bypassing the need to calculate $k_1$ and $k_2$, I could get to $t=2019$ in under two minutes, thanks!

For the curious, $k(2019)$ is

2305290672102308631501600234772689901495331656296010173782609457211747
7589012645449972855113002723152850266996581249955310937900637196208377
6015656037190992015601992708978972950218730384956136982230018199914037
1873790474857914308090439690528149039878522176523214171723899120931680
1407795795740287175481595074888464242169114272889833455443538979070710
7954615588986518937269460499977097780936892890288486500115267711198795
7752458754886945509455939738184415246125385661077598946496962529694021
3807498060952467101009725056900507200381670539199960267610955917970647
7348799285007520324333753433137317268595827312669270283710749289135338
3955488775416701421703591611585762587057816965055493289203079657757930
5552781639283256208264236157412839744713189755433693182114657440937393
5151735730964047333464200133046259636266617568495188850439992270539482
5070877950569111185484686258280683360985364614068620085244473016206039
9671853656249766670780202123346133265126530063266776108759382094754654
7716756458855458762042468590857137475911810094709371114227296091704480
6711606499107516880961144418896377536483208496898216007308760220924549
0972474888415801145088826737967372992873259567856816687494684460704424
3173061490180787964985981600770130719077612467850081453816286747633594
4284192328266852157788811299072458199422958623051583550247028984113634
4318289858861052813363039650908790965740078659153247276116386453200334
4836368400516024727032229892621807743635165529464487581545206230448918
1409645082500520804695354024823612306132917021276679585259953063129411
2545858077944461034768509061573193702273821820349478826128151042412868
5956793739278347138201495237865669448730673402603953205685107039200080
8952929651674242338774206988881423049199670391597860260553207517719017
9002932994455476535864508393906288302896457722437946004108041176775861
4329745301223902630302872947877380477704859782754757564959523661085897
7676261776516245911952437104048944340050558070801081399143586315076037
3235657211779132129451895845453642989758910041413588006513
Posted 5 years ago

Hi, just one more optimization after re-reading your post: We don't even have to ask Wolfram for the multiplicative order, you already calculated it. $$\it{ord}_{10^t} 71 = \frac{10^t}{(8)(5)}$$ Thanks again for all of the details working through the problem.

POSTED BY: William Isaacs
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract