0
$\begingroup$

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.

$\endgroup$
6
  • 3
    $\begingroup$ Iterated squaring works well. $2^8=256\equiv 62\pmod {97}$ and so on. $\endgroup$
    – lulu
    Feb 17, 2021 at 20:30
  • 4
    $\begingroup$ 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. $\endgroup$
    – Steven Stadnicki
    Feb 17, 2021 at 20:30
  • $\begingroup$ @StevenStadnicki these are some advanced topics for me . $\endgroup$
    – PNT
    Feb 17, 2021 at 20:33
  • $\begingroup$ $2=14'^2\pmod{97}$ so $2^{48}=14^{96}\pmod{97}$ and that is $1$ by Fermat's Little Theorem $\endgroup$
    – Empy2
    Feb 17, 2021 at 20:36
  • $\begingroup$ 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\ \ $ $\endgroup$
    – Bill Dubuque
    Feb 17, 2021 at 20:46

0

Reset to default

Browse other questions tagged .