Prove that $n$ doesn't divide $2^n - 1$ for any integer $n$ bigger than $1$.
Thanks in advance! Any questions, please comment!
Asked
Active
Viewed 240 times
3
TMM
- 9,976
user2977079
- 303
1 Answers
7
Hint: $n$ is obviously odd. Now let $p$ be the least prime divisor of $n$. Then $2^{n}=1 \mod p$ and $2^{p-1}= 1 \mod p$. But $p-1$ and $n$ are coprime.
user68061
- 3,827
-
So, primitive roots? – user2977079 Feb 05 '14 at 20:45
-
no, you don't need them, but they make things easier :) to go without primitive roots consider the smallest $k$ such that $2^k-1$ is divisible by $p$ – user68061 Feb 05 '14 at 20:47
-
So $2^{p-1}$ cannot be congruent to $2^n$ modulo a prime because they are coprime? – Joao Oct 27 '14 at 03:45