Show that: $97\mid (2^{48})-1$
Verify $97\mid 2^{48}-1$
I am so confused with how mods worked. Can someone please work out this problem in the simplest terms possible? Thank you so much!
$\endgroup$ 35 Answers
$\begingroup$There is a lot of relevant theory that makes calculation unnecessary. But let us calculate, in an efficient way, using an ordinary calculator.
We have $2^6=64$. Now let us find the remainder when $2^{12}$, that is, $(2^6)^2$, is divided by $97$.
Square $64$ on the calculator. We get $4096$. Divide by $97$ on the calculator. Mine gives $42.22680412$. Subtract $42$ from this on the calculator, and multiply the result by $97$. We get $22$. On a different calculator, we might get a number very close to $22$, like $21.9999997$. We would still know the remainder is $22$.
So $2^{12}\equiv 22\pmod{97}$. Now find the remainder when $2^{24}$, that is, $(2^{12})^2$, is divided by $97$.
On the calculator, square $22$. Divide by $97$. We get something like $4.989690722$. On the calculator, subtract $4$, and multiply by $97$. We get $96$. Thus $2^{24}\equiv 96\pmod{97}$.
Now we can either note that $96\equiv -1\pmod{97}$, and conclude that $2^{48}\equiv (-1)^2\equiv 1\pmod{97}$.
Or else we can blindly calculate. Square $96$, divide by $97$. We get $95.01030928$. Subtract $95$, multiply by $97$. We get $0.999999791$. The remainder is $1$.
$\endgroup$ $\begingroup$$\,\color{#c00}{2 = 14^{\large 2}} - 2(97),\,$ so $\, {\rm mod}\,\ 97\!:\ \color{#c00}{2\equiv 14^{\large 2}}\,\Rightarrow\,\color{#c00}2^{\large 48}\equiv (\color{#c00}{14^{\large 2}})^{\large 48}\equiv 14^{\large 96}\equiv 1\,$ by little Fermat. $ $ QED
$\endgroup$ $\begingroup$Without any of the relevant theory, like Andre's answer.
Using Difference of Two Squares factorization several times,
$2^{48} - 1 = (2^{24} + 1)(2^{12} + 1)(2^6 + 1)(2^3 + 1)(2^3 - 1)$
$97$ is prime, so it's clear $97$ doesn't divide any of the latter three factors (since $97$ is greater than them)
Furthermore, note that $2^{12} + 1 = 4097$, so it's easy to see that $97$ does not divide that either.
Thus, it must be the case that $97 \mid 2^{24} + 1$. Therefore, we wish to show that $2^{24} \equiv -1 \pmod {97}$
Through brute force, we find that $2^{12} \equiv 22 \pmod {97}$. Brute forcing again, $(2^{12})^2 = 2^{24} \equiv 22^2 \equiv -1 \pmod {97}$, as desired.
$\endgroup$ $\begingroup$Hint: Since $97$ is prime, by Fermat's little theorem it follows that $$2^{96} \equiv 1 \pmod{97}$$ Now notice that $48 \times 2 = 96$ and take it from there.
Side note: I'm reluctant to give a full worked solution to this problem. If you're still stuck, feel free to ask questions and I'll be happy to help out.
$\endgroup$ 4 $\begingroup$(2^3-1)(2^3+1)(2^6+1)(2^12+1)(2^24+1)(2^48+1) now take (2^3-1)(2^3-1)=(8-1)(8+1)=7*9=63 now take (2^6+1)=64 (2^12+1)=4097 (2^24+1)=16777216+1=16777217 that is divisible by 97 we can break the whole set of things into 6 parts and can try them to prove.this is lengthy method but as the question have a²-b² formula i think it will have to work
$\endgroup$
