Prove that $\gcd(2^n-1,n)=1$ with :

189 Views Asked by At

$n=pq$ with $p,\ q$ two different odd prime numbers such that $p<q<2p$.

Notice that $2^n-1\equiv 0 \pmod{2^n-1} \Leftrightarrow 2^n\equiv 1 \pmod{2^n-1}$.

So the order of $2$ (invertible) in $(\mathbb{Z}/(2^n-1)\mathbb{Z})^{\times}$ divides $n=pq$. It also divides $\phi(2^n-1)$. We can deduce that this order divides $\gcd(\phi(2^n-1),n)$ but it will be difficult to conclude.

But we can also notice that the integer $2^n-1$ is necessarily odd so we can write $2^n-1=l_1^{\xi_1}...l_k^{\xi_k}$ with $l_i$ odd prime numbers.If we do not find $p$ and $q$ in that list it will be right.

$2^{n}-1=(2^{pq}-1)=(2^p-1)K=(2^q-1)K'$ with $K,K'\in \mathbb{Z}$. (What will be the expression $K'$ and $K$ in that case ??)

However by FlittleT we have for $2\in (\mathbb{Z}/p\mathbb{Z})^{\times}$ : $2^{p-1} \equiv 1 \pmod p$ (same for $q$) so $2^p \equiv 2 \pmod p$ (true for $2 \in \mathbb{Z}/p\mathbb{Z}$). So $p$ does not divide $2^p-1$ (same $q$ does not divide $2^q-1$). But how to conclude ?

I try to develop $K$ and $K'$ and prove that $p$ or $q$ does not divide dem but it's difficult to factorize these expressions because of prime numbers.

Thanks in advance !

2

There are 2 best solutions below

6
On BEST ANSWER

I think all we need is Fermat's little theorem. We know that (as you said) $$2^{pq} \equiv 2^q \pmod p$$ So $$2^{pq}-1 \equiv 2^q -1\pmod p$$ And so we want to know if $p|(2^q-1)$.

But if $$2^{q}-1 \equiv 0\pmod p$$ then by FLT again, $(p-1)$ and $q$ have a common factor. But $q>p$ and $q$ is prime so we can't have such a common factor.

Now if we switch the primes, we get that $(q-1)$ and $p$ have a common factor.So then as $p$ is prime we must have $p|(q-1)$.
But again this is impossible as $(q-1)<2p$.
So we get that neither $p$ nor $q$ can divide $2^n -1$ so we're done.

1
On

Take $n=3.7=21$ Then $2^n-1=2^{21}-1$ their $\gcd\neq1$.