Login

u/ohwaitwhat37

r/matiks r/QuizPlanetGame
▲ 4 r/matiks

the brackets do not indicate a matrix

answer is >!16, because the sum of all n choose k such that k < n where k is even is equal to the sum of all n choose k where k is odd, therefore each of them are half the total sum of all n choose k. therefore, the sum from n = 0 to n = 32 for 66 choose 2n is equal to 66 choose 0 + 66 choose 2 + 66 choose 4... + 66 choose 64. however we are missing 66 choose 66 so we need to remember to subtract 1 from our final answer. the sum of all 66 choose k where k is even is 2^65 (because the sum of all n choose k is just 2^n, so 2^66/2 = 2^65) and the sum of all 65 choose k where k is even is 2^64. 2^65 - 2^64 = 2^64, so now we just need to evaluate 2^64 - 1 mod 67. Note that by Euler's totient, 2^66 is congruent to 1 mod 67, which is congruent to 68 mod 67, so dividing both sides by 2 gives 2^65 congruent to 34 mod 67 and 2^64 is congruent to 17 mod 67. Therefore, the final answer is 17 - 1 = 16.!<

i.redd.it
u/ohwaitwhat37 — 2 months ago
▲ 19 r/matiks

the brackets do not indicate a matrix

answer is >!16, because the sum of all n choose k such that k < n where k is even is equal to the sum of all n choose k where k is odd, therefore each of them are half the total sum of all n choose k. therefore, the sum from n = 0 to n = 32 for 66 choose 2n is equal to 66 choose 0 + 66 choose 2 + 66 choose 4... + 66 choose 64. however we are missing 66 choose 66 so we need to remember to subtract 1 from our final answer. the sum of all 66 choose k where k is even is 2^65 (because the sum of all n choose k is just 2^n, so 2^66/2 = 2^65) and the sum of all 65 choose k where k is even is 2^64. 2^65 - 2^64 = 2^64, so now we just need to evaluate 2^64 - 1 mod 67. Note that by Euler's totient, 2^66 is congruent to 1 mod 67, which is congruent to 68 mod 67, so dividing both sides by 2 gives 2^65 congruent to 34 mod 67 and 2^64 is congruent to 17 mod 67. Therefore, the final answer is 17 - 1 = 16.!<

u/ohwaitwhat37 — 2 months ago