Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

5 Answers 5

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

share|improve this answer
    
(+1) I was about to post a similar answer but you beat me to it :) –  TMM Jan 21 '13 at 21:56
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

$\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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.