0
$\begingroup$

$a =\gcd(2^m - 1; 2^n - 1)$. Why $2^n ≡ 1$ (mod $a$) and $2^m ≡ 1$ (mod $a$)?

$\endgroup$
  • $\begingroup$ Nothing to do with $\gcd$ in particular. Recall the definition of $x \equiv y \pmod{k}$. $\endgroup$ – Daniel Fischer Oct 17 at 17:57
  • 2
    $\begingroup$ If $a$ is the gcd then it is a divisor. So, $2^m-1\equiv 0 \pmod a$, and so on. $\endgroup$ – lulu Oct 17 at 17:57
  • $\begingroup$ Simply because $2^n-1$ and $2^m-1\equiv 0\pmod a$. $\endgroup$ – Bernard Oct 17 at 17:57
  • $\begingroup$ $2^n\equiv1\pmod a$ means $a\mid(2^n-1)$. $\endgroup$ – Lord Shark the Unknown Oct 17 at 17:57
  • $\begingroup$ ahhh, of course, i understood, tq $\endgroup$ – mhmhhmhmhm Oct 17 at 17:58
0
$\begingroup$

If $a=\gcd(2^m-1;2^n-1)$, then in particular $a$ divides $2^m-1$ and $2^n-1$. That is, there exists integers $i,j$ such that $2^m-1=ai$ and $2^n-1=aj$. Thus,

$$2^m-1\equiv ai=0\pmod a$$

and so

$$2^m\equiv 1\pmod a,$$

etc. Recall that, by definition, $c\equiv d\pmod p$ if and only if $p$ divides $c-d$.

$\endgroup$

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