# Problem with congruence relations

Show that $97|2^{48}-1$

So far I managed to use Fermat's Little Theorem where I got

$2^{96}≡1\pmod {97}$

Which I then reconstructed as

$2^{48}*2^{48}≡1\pmod {97}$

And I got stuck here. I'm pretty sure I need to get

$2^{48}-1≡0 \pmod {97}$

as the end result, but I have no idea how to get there. Any help would be greatly appreciated.

-
I don't think Fermat's Little Theorem is enough in this case. Which will probably make the result a tad uglier... – Mike Jan 21 '13 at 21:00
Use \pmod {97} to get the LaTeX right. – Paul Raff Jan 21 '13 at 21:11

One can compute, or use a little theory. Since $97$ is of the shape $8k+1$, it follows that $2$ is quadratic residue of $97$. But then $2^{(97-1)/2}\equiv 1 \pmod{97}$.

-
(+1) I was about to post a similar answer but you beat me to it :) – TMM Jan 21 '13 at 21:56

One naive way:

$$2^{48}-1=\left(2^{24}-1\right)\left(2^{24}+1\right)$$

But

$$2^{24}+1=\left(2^8\right)^3+1=\left(2^8+1\right)\left(2^{16}-2^8+1\right)$$

$$2^7=128=31\pmod{97}\Longrightarrow 2^8=62\pmod{97}\Longrightarrow$$

$$2^{16}=(2^8)^2=62^2=61\pmod{97}\Longrightarrow$$

$$2^{16}-2^8+1=61-62+1=0\pmod{97}$$

-

There are a number of results on primitive roots modulo primes, but the easiest way to do this is to just find the order of $2$ mod $97.$ The only possibilities are divisors of $96.$ First check $2^{12} \equiv 22 \mod 97$ (easy calculation) and then $2^{24} \equiv -1 \mod 97,$ so $2^{48} \equiv 1 \mod 97,$ as desired.

-

$\rm mod\,\ {97}\!:\ 2\equiv 196\equiv 14^2.\$ Now, taking $48$'th powers,

therefore $\rm\: 2^{48}\equiv\, (14^2)^{48}\equiv 14^{\color{}{96}}\equiv 1\,\ (mod\ 97) \$ by little Fermat.

-

You're half right that you want to get to

$$2^{48} \equiv 1 \pmod {97};$$

what you really want is

$$2^{48} \equiv \pm 1 \pmod {97}$$

To show this, we need a little more, and a contradiction-style proof works well. Suppose $2^{48} \equiv k \pmod {97}$ but $2^{96} \equiv 1 \pmod {97}$. This implies that $k^2 \equiv 1 \pmod {97}$ from which you can infer that $k \equiv \pm 1 \pmod {97}$ by checking the 97 cases or showing that since $k^2 \equiv 1 \pmod {97}$ then $k^2-1 = 97n$ for some $n$, but since $k^2-1 = (k+1)(k-1)$ then either $k+1$ or $k-1$ must be divisible by 97 (since 97 is prime).

-