5
$\begingroup$

Is there any easier (less no. of steps or calculations) proof for this using congruences: $89|2^{44}-1$. My proof: $$2^6\equiv-25\mod89$$ $$2^5\equiv32\mod89$$ Now square both equations: $$2^{12}\equiv625\equiv2\mod89$$ $$2^{10}\equiv-44\mod89$$ Now multiplying: $$2^{22}\equiv-88\equiv1\mod89$$ Since $2^{44}-1=(2^{22}+1)(2^{22}-1)$, it is proved.

$\endgroup$
5
  • 1
    $\begingroup$ You want a solution that takes less than 3-5 steps? Exactly which calculations are costly for you? The modulo or the raising to a power? $\endgroup$
    – Axoren
    Jan 18, 2015 at 15:52
  • $\begingroup$ @Axoren: the calculations like finding the remainder after squaring both equations. $\endgroup$
    – zed111
    Jan 18, 2015 at 15:54
  • 3
    $\begingroup$ If one uses some theory, one does not need to calculate at all. Note that $2$ is a quadratic residue of $89$. Now use Fermat's Theorem. $\endgroup$ Jan 18, 2015 at 15:59
  • $\begingroup$ How do we note $2$ is a quadratic residue of 89? Although that does finish quite nicely. $\endgroup$
    – Asinomás
    Jan 18, 2015 at 16:06
  • 1
    $\begingroup$ Standard result, $2$ is a QR of primes of the form $8k\pm 1$, and a NR for primes of the form $8k\pm 3$. $\endgroup$ Jan 18, 2015 at 16:53

2 Answers 2

1
$\begingroup$

Hint: $2^{44}-1=(2^{22}-1)(2^{22}+1)=(2^{11}-1)(2^{11}+1)(2^{22}+1)=2047\cdot2049\cdot(2^{22}+1)=$ $=(23\cdot89)\cdot2049\cdot(2^{22}+1).\quad$ Of course, this assumes a certain familiarity with the powers of $2$.

$\endgroup$
1
$\begingroup$

Essentially all you would like to know is if $2$ is a primitive root $\bmod 89$. We know that primitive roots exist because $89$ is prime. This is generally hard to do. Here is a question discussing how to find primitive roots.

In this case it turns out $2^{11}$ is already congruent to $1\bmod 89$ so $2^{44}$ will also..

$\endgroup$
2
  • $\begingroup$ $\;2^{11}=1\pmod{89}\implies 2\;$ is not a a primitive root $\;\pmod{89}\;$ , of course. $\endgroup$
    – Timbuc
    Jan 18, 2015 at 16:58
  • $\begingroup$ I like the intuitiveness of this answer. Given $2^{11}\equiv1\mod89$ and $11|44$, then $2^{44}\equiv1\mod89$, therefore of course $2^{44}-1\equiv0\mod89$. I'm left curious how @Jorge got to $2^{11}\equiv1\mod89$ in the first place, though. $\endgroup$
    – wtr
    Mar 22, 2017 at 18:33

Not the answer you're looking for? Browse other questions tagged .