3 ms·
2^34240923842043983204982-1 is divisible by 3.
by fdej 11y ago
2^34240923842043983204982-1 is divisible by 3.
- cdelsolar 11y agoHow'd you do that?
- dsr_ 11y agoWrite 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.
- nickodell 11y agoHow did you write out the number? It's 10307545155701210591839 digits long.
- morsch 11y agoI'll get back to you once I find a piece a paper large enough to write down the 10 sextillion decimal digits.
- LeifCarrotson 11y agoThat'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).
- cousin_it 11y agoThe 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.
- tejapr 11y agoa ^ (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.
- deleted 11y ago[deleted]