Is $2^{1093}-2$ a multiple of $1093^2$?

Question

I can't solve this problem; it may be easy though.

Is the number $2^{1093} -2$ a multiple of $1093^2$?

I do appreciate any kind of help.

Answer 1

You can work this sort of thing out for number of the form $2^{2^n}$ by squaring the previous result and taking this modulo $1093^2$

   n    2^n mod 1194649
   1    2
   2    4
   4    16
   8    256
  16    65536
  32    204141
  64    606814

etcetera,

and then noting that $2^{1093}=2^{1024}2^{64}2^{4}2^{1}$. And yes, it is true.

Answer 2

Below I explain the unmotivated hand calculation in Hardy and Wright (appended below).

If $\rm\ {\hat c} =\: c^{-1}\pmod{p}\ $ is "simpler" than $\rm\:c,\:$ then to verify $\rm\ c^n \equiv\: d\ $ it may be simpler to use $\rm\: {\hat c}^n.$

Notice $\rm\ c\ {\hat c}\ \equiv\ 1 + a\ p\ \Rightarrow\ c^n\ {\hat c}^n\ \equiv\ 1 + n\ a\ p\pmod{p^2}\quad $ by the Binomial Theorem.

Therefore $\rm\ \ \ c^n\ \equiv\ d\ \iff\ d\ {\hat c}^n\ \equiv\ 1 + n\ a\ p\pmod{p^2}\quad\ (\Leftarrow\:\: $ by cancel $\rm\ {\hat c}^n $ from this & above)

E.g. $\rm\ \ c\ {\hat c}\ \equiv\ 2^{26}\ (-9)\ \equiv\ 1 + 469\ p\pmod{p^2},\ \ p = 1093, \ $ by equations $\:\#3,4,5\:$ in $\rm\:H\&W\:.$

so $\rm\: (2^{26})^7\: \equiv\: {-}1\ \iff\: {-}(-9)^7\ \equiv\ 1\ +\ 7\cdot 469\ p\pmod{p^2}$

In equation $\rm\: \#6,\ \ H\&W\:$ calculate $\rm\ \ 1\ +\ 7\cdot 469\ p\ \equiv\ 1+4\ p$

In equation $\rm\: \#2,\ \ H\&W\:$ calculate $\rm\: -(-9)^7 \equiv\ 3^{14} \equiv\ 1 + 4\ p\quad$

Thus $\rm\: 2^{182}\: \equiv\: -1\ \Rightarrow\ 2^{1092}\: =\ (2^{182})^6\: \equiv\ (-1)^6\: \equiv 1\pmod{p^2}\quad $ QED

In terms of Hensel / Newton's lemma, we lift a "simple" inverse $\rm\ (mod\ p)\ \ to\ \ (mod\ p^2)\:.$

Answer 3

Yes. According the Wikipedia article linked by André Nicolas, 1093 is one of only two known primes $p$ for which $p^2$ divides $2^{p}-2$.

The other known prime is 3511. It is known from computer searches that if any other so-called "Wieferich primes" exist, they must exceed $6.7×10^{15}$.

Answer 4

(Note: This answer essentially duplicates the one given by Bill Dubuque. This is due to the merger of a question asked Mar 2 '15 with a duplicate from Jan 9 '12.)

In a 1983 paper in The Mathematical Intelligencer titled simply "1093," Paolo Ribenboim gives the following proof, with credit to Landau:

Let $p=1093$.

$$3^7=2187=2p+1$$ so squaring

$$3^{14}\equiv4p+1\pmod {p^2}\qquad(*)$$ On the other hand, $$2^{14}=16384=15p-11$$ so $$2^{28}\equiv-330p+121\pmod{p^2}$$ hence $$3^2\times2^{28}\equiv-1876p-4\pmod{p^2}$$ and dividing by $4$ $$3^2\times2^{26}\equiv-469p-1\pmod{p^2}$$ Raising now to the $7^\text{th}$ power:

$$3^{14}\times2^{182}\equiv-4p-1\pmod{p^2}$$

and taking $(*)$ into account

$$2^{182}\equiv-1\pmod{p^2}$$

Finally, raising to the $6^\text{th}$ power,

$$2^{1092}\equiv1\pmod{p^2}$$

One point I found necessary to think about is $$(1+469p)^7\equiv1+7\cdot469p=1+3283p\equiv1+4p\pmod {p^2}$$ Aside from that, everything is straightforward calculation with small numbers. How Landau came up with this approach is the real marvel here.

It's perhaps worth noting that this proof does not rely on $1093$ being prime. It only uses the fact that it's not divisible by either $2$ or $3$ (in the steps where you divide by $4$ and cancel the $3^{14}$.)

Answer 5

This is tractable by hand by brute force: You repeatedly square numbers starting from 2, and take remainers mod $1093^2 = 1194649$ until you come to $$ 2^{1024} \equiv 917050 \mod 1194649$$ then you multiply that by your (remembered) residues of $2^{64}$ and $2^4$ and you find that $ 2^{1092} = 917050 \cdot 606814 \cdot 65536 = 1 \mod 1194649$.

So, $$ 2^{1092} -1 = k\cdot (1093)^2 \Longrightarrow (1093)^2 |2^{1092} -1$$

But that is not the way you should do this problem in a number theory course. The question becomes ($1093$ being prime) , when does $$ p^2 \mid a^q - 1 $$

I'm not sure how to answer that easily, but I strongly suspect there is an easy way.