Show that the least prime divisor of $2^{17}-1$ is $2^{17}-1$ itself.
This question is really anoying. Let $N=2^{17}-1$. What I know is that if $q\mid N$, then $q=34k+1$ for some $k \in \Bbb{N}$ and $q \equiv \pm1 \pmod 8$. Therefore,
$$q \equiv 2k+1 \equiv \pm1 \pmod 8$$
We get $k \equiv -1, 0 \pmod 4$. So $q=136x+1$ or $q=136x-33$ for some $x \in \Bbb{N}$.
This is all I know about finding the prime divisor of the form ${2^{p}-1}$, which might be the Mersenne number. But do I have to just substitute each possible value of $q$ into $N$ in order to show that it ultimately doesn't have any prime divisors other than $N$ itself? It takes so much time and effort. And I don't think the problem is just to make students tediously substitute each case one by one(if it is, then I'm so frustrated).
So the question: is there any more time-saving way to distinguish certain types of Mersenne number without goint too far from my basic understading of Number Theory? Or should I just subsitute one by one and that's the best choice I can take?
Thanks!
Edited This was a question that baffled me about few months ago, and after studying the case for perfect numbers, now I do know that $2^{17}-1$ is a Mersenne number(related to the perfect number $8589869056$). But I still think just memorizing the case doesn't give me full insight into this area.
Best Answer
Let $p|2^{17} - 1$, then we have $2^{17} \equiv 1 \pmod p$, but we also have from Fermat's Little Theorem $2^{p-1} \equiv 1 \pmod p$.
From Lagrange Theorem for group order we get that $2^{\gcd(p-1,17)} \equiv 1 \pmod p$.
Obivously the greatest common divisor is $17$, because otherwise (if the gcd were $1$) then $2 \equiv 1 \pmod p$, which is impossible.
Then we have $17 \mid p-1$ and because $p-1$ is even we have $34\mid p-1$. So we need to check all prime numbers of the form $p=34k + 1 \quad \forall k \in \mathbb{N}$ such that $p \in (1,\sqrt{2^{17} - 1}]$. Which reduces the number of divisors to check. Actually there are just $4$ primes in this inteval, those are $103, 137, 239, 307$. You can check that none of them divides $2^{17} - 1$, implying that $2^{17} - 1$ is prime.
Also you can check how Euler proved that $2^{31} - 1$ is prime, and apply the same method on $2^{17} - 1$.
Actualy $2^{17} - 1 = 131071$ isn't that big number, even without knowledge in number theory it isn't so much hord work to do.
And at last as other users have suggested use Lucas-Lehmer Test.