CRT, totient and Fermat

Questions 1 to 5 of 8

1. 1. Two conditions are x ≡ 2 (mod 4) and x ≡ 3 (mod 6). Which statement is correct?

   x = 22 satisfies both, because 22 mod 4 = 2 and 22 mod 6 = 4x = 14 satisfies both, because 14 mod 4 = 2 and 14 mod 6 = 3No x exists, because the gcd of 4 and 6 is 2, and 2 does not divide 3 - 2 = 1x ≡ 10 (mod 12) is the answer, because 10 mod 4 = 2 and 10 mod 6 = 3
2. 2. What is Euler's totient phi(360)?

   Type a number.

3. 3. Which statements about Euler's totient are true?

   Pick every answer that is true.

   phi(1) = 0phi(12) = 4phi(36) = 12phi(8) = 3
4. 4. An AI wrote result = result * (p - 1) / p; to compute phi of the prime 999999999989. Why is this wrong?

   It is right, because the order of multiplying and dividing does not matterIt divides by p too early, so the answer is always too smallresult * (p - 1) is about 10^24, which overflows a 64-bit integer, so the division works on a wrong valueIt uses p - 1 instead of p, so the formula is wrong
5. 5. What is phi(1000000007), where 1000000007 is prime? Give the number.

   Type a number.