8
$\begingroup$

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.

  • 0
    As a consequence of the merger I deleted some comments that were duplicating comments on the earlier version.2015-03-03

5 Answers 5

10

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.

6

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)\:.$ enter image description here

4

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}.

3

(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}$.)

  • 0
    Pretty nice. Not the general method I had guessed would exist, but more clever than my brute-force approach.2015-03-03
2

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.

  • 0
    For the last remark: cases a>p can be generated to arbitrary powers of $p$; but the cases a are difficult and for this there is no easy way (known). An easy example however is $p=11,a=3$ making $11^2|3^5-1$ . Look at "fermat-quotients"; there are tables for everal "brute-force" results online available. Theres also one example known where $p^3 | a^{p-1}-1 $: $113^3 | 68^{112}-1 $2015-03-02