Is 2^131 - 1 a prime number? if so how can i proof it, or if no how?
In the general is there a way for primality check for a 2^n - 1
Thanks
Asked
Active
Viewed 61 times
1
frogatto
- 115
-
1google: mersenne primes – Shobhit Oct 13 '13 at 15:29
-
3It's not prime, it's divisible by $263$ (the other prime factor is $10350794431055162386718619237468234569$). Generally, for Mersenne numbers, the Lucas-Lehmer test is the way. – Daniel Fischer Oct 13 '13 at 15:30
-
131 looks like a prime to me, so the basic requirement for messerne primes is satisfied. Yet it isn't a prime. – John Dvorak Oct 13 '13 at 15:32
-
@DanielFischer Thanks good answer! but how you calculate other prime factor?! – frogatto Oct 13 '13 at 15:34
-
Check that $\dfrac{2^{131}-1}{263}$ is a prime number using some other test. (Baillie-PSW + Pocklington certificate) – Daniel Fischer Oct 13 '13 at 15:39
-
@DanielFischer okay thanks! – frogatto Oct 13 '13 at 15:41
-
Reverse engineering Daniel's factor: $p=263\equiv7\pmod8$, so by (an extension of) quadratic reciprocity $2$ is quadratic residue modulo $p$. Therefore $$2^{(p-1)/2}=2^{131}\equiv1\pmod{263}.$$ – Jyrki Lahtonen Oct 13 '13 at 15:42
-
Or the other way round, $131 \equiv 3 \pmod{4}$, and $2\cdot 131 +1 = 263$ is prime, hence $263 \mid 2^{131}-1$. – Daniel Fischer Oct 13 '13 at 15:44