News for hackers. Stuff that matters.
Re:2^74207281-1 is Prime by owenversteeg on Tuesday January 19, 2016 @02:35PM (#10933312)
Interestingly, if the alien's memorized number was significantly larger (e.x. tens of billions of digits) we would not be able to verify it. It took three and a half days to verify the correctness of M74207281 on two 18-core Xeon servers, and with speed increases in computing slowing down it may be a very long time before we are able to verify a number that large.

So, nothing. The alien could say "Oh yeah, we have 2^34240923842043983204982-1" and they could be absolutely correct but there's nothing we could do to know.

Or, if their number was big but not that big, it might be able to be verified in, say, a year, in which case it might win the EFF's prize and could possibly get some other sort of prize money. So, $150k + some undefined amount.

Re:2^74207281-1 is Prime by fdej on Tuesday January 19, 2016 @03:12PM (#10933600)
2^34240923842043983204982-1 is divisible by 3.
Re:2^74207281-1 is Prime by cdelsolar on Tuesday January 19, 2016 @03:41PM (#10933833)
How'd you do that?
Re:2^74207281-1 is Prime by cousin_it on Tuesday January 19, 2016 @04:46PM (#10934318)
The sequence 2^n mod 3 goes 2, 1, 2, 1, 2...

That's how you solve all problems of this form. For any a and b, a^n mod b eventually becomes periodic as n grows. It's easy to prove because there's only a finite number of possible remainders mod b. As an exercise, calculate 3^1000000 mod 7.

Re:2^74207281-1 is Prime by tejapr on Tuesday January 19, 2016 @06:06PM (#10934806)
a ^ (n - 1) ~= 1 mod n if n is prime, Fermat's Little Theorem.

3 is prime. 34240923842043983204982 is divisible by 3 - 1 = 2.

ab mod n = [a mod n * b mod n] mod n

So, we can automatically infer that 2 ^ 34240923842043983204982 ~= 1 mod 3.

After subtracting 1, it will be divisible by 3.

Alternatively, you could notice that 2 ^ 2 ~= 1 mod 3, which implies 2 ^ 4 ~= 1, 2 ^ 6 ~= 1, so 2 ^ all even powers will be congruent to 1 modulo 3.

So 2 ^ x - 1 will always be divisible by 3 for even x.

Re:2^74207281-1 is Prime by dsr_ on Tuesday January 19, 2016 @03:56PM (#10933950)
Write out the number in decimal, add the digits together: if the result is larger than a single digit, repeat. When you have a single digit, if it is 3, 6 or 9, the number is divisible by 3.

The proof is left as an exercise for the student.

Re:2^74207281-1 is Prime by LeifCarrotson on Tuesday January 19, 2016 @04:41PM (#10934283)
That's the divisibility check for 3, yes, but I am pretty sure fdej didn't write that number out in decimal. The proof doesn't work with exponents. You'd have to represent the number in base 10 for digit summing to work.

To check, 2^6-1=63 is divisible by three (it might work), but 2^9-1 has a sum of 12 and a value of 511, which is not divisible by three (it's 170 * 3 = 510 + 1).

Re:2^74207281-1 is Prime by morsch on Tuesday January 19, 2016 @04:35PM (#10934236)
I'll get back to you once I find a piece a paper large enough to write down the 10 sextillion decimal digits.
Re:2^74207281-1 is Prime by nickodell on Tuesday January 19, 2016 @04:32PM (#10934220)
How did you write out the number? It's 10307545155701210591839 digits long.