# A better method to prove that $97 \mid 2^{48}-1$ [duplicate]

Proving that a given numbers is divisible by an other number is often simple but when it comes to big numbers i don’t know how to deal with them.

Prove that $$97 \mid 2^{48}-1$$.

My Attempt:

$$2^{12} \equiv 22 \mod 97 \iff (2^{12})^{4} \equiv 22^4\equiv1 \mod 97$$ $$\iff 2^{48} \equiv 1 \mod 97 \iff 97 \mid 2^{48}-1$$

It seems short but the problem here is that $$2^{48} \equiv 1 \mod 97$$ Should be proven, but i’ve just used a calculator to prove it, So is there a better method to prove thi type of problem.

• Iterated squaring works well. $2^8=256\equiv 62\pmod {97}$ and so on.
– lulu
Feb 17, 2021 at 20:30
• What you've done here is totally legitimate; there are reasons why $97|2^{48}-1$ (see Fermat's Little Theorem and the quadratic reciprocity condition ), but you don't need to know 'why' to show that it's true. Feb 17, 2021 at 20:30
• @StevenStadnicki these are some advanced topics for me .
– PNT
Feb 17, 2021 at 20:33
• $2=14'^2\pmod{97}$ so $2^{48}=14^{96}\pmod{97}$ and that is $1$ by Fermat's Little Theorem Feb 17, 2021 at 20:36
• See modular order reduction in the linked dupe for the general idea, and see the many posts linked there for examples. In particular this linked answer works here since $\,2\equiv 14^2\ \$ Feb 17, 2021 at 20:46