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


closed as off-topic by user21820, Arnaud D., kimchi lover, 1 0, postmortes Nov 6 at 6:13

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – user21820, Arnaud D., kimchi lover, 1 0, postmortes
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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

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$.


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