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

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

• Nothing to do with $\gcd$ in particular. Recall the definition of $x \equiv y \pmod{k}$. – Daniel Fischer Oct 17 at 17:57
• If $a$ is the gcd then it is a divisor. So, $2^m-1\equiv 0 \pmod a$, and so on. – lulu Oct 17 at 17:57
• Simply because $2^n-1$ and $2^m-1\equiv 0\pmod a$. – Bernard Oct 17 at 17:57
• $2^n\equiv1\pmod a$ means $a\mid(2^n-1)$. – Lord Shark the Unknown Oct 17 at 17:57
• ahhh, of course, i understood, tq – 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$$
$$2^m\equiv 1\pmod a,$$
etc. Recall that, by definition, $$c\equiv d\pmod p$$ if and only if $$p$$ divides $$c-d$$.