Chinese Remainder Theorem & Fermat's Little Theorem

CRT Basics

100

What does CRT stand for?

Chinese Remainder Theorem

200

If n₁ and n₂ are not coprime, does CRT guarantee a solution to x ≡ a₁ (mod n₁) and x ≡ a₂ (mod n₂)?

No, only if a₁ ≡ a₂ (mod gcd(n₁, n₂)).

300

Explain why CRT requires pairwise coprime moduli.

Ensures a unique solution exists (otherwise, contradictions may arise).

400

What is the least three-digit positive whole number that is 4 (mod 7), 5 (mod 8), 6 (mod 9)?

501

500

Find the smallest x such that x ≡ 1 (mod 2), x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 4 (mod 7), and x ≡ 5 (mod 11). 

1523

FLT Basics

100

State Fermat's Little Theorem for a prime p and integer a. 

If p is prime and a is not divisible by p, then
a^p-1 ≡ 1 (mod p)

200

What is 2¹⁰ (mod 11) using FLT?

1

300

If p is prime, what is a^P (mod p) for any integer a?

a (mod p)

400

What proof technique is most commonly used to prove Fermat's Little Theorem?

Mathematical Induction

500

Compute 5²⁰¹ (mod 101) using FLT.

5

CRT Applications

100

If x≡1 (mod 2) and x≡2 (mod 3), is there a solution?

Yes (since 2 and 3 are coprime).

200

Solve x ≡ 4 (mod 5) and x ≡ 3 (mod 7).

x ≡ 24 (mod 35).

300

A number leaves remainder 1 when divided by 3, 2 when divided by 5, and 0 when divided by 7. Find the smallest such number. 

7 

400

A number is divisible by 7, leaves remainder 3 when divided by 11, and remainder 5 when divided by 13. Find the smallest such number.

707

500

A number is 2 (mod 3), 3 (mod 5), 4 (mod 7), and 5 (mod 11). Find the smallest such number > 1000.

1859

FLT Computations

100

Compute 5³⁶ (mod 37) using FLT.

1 (since 37 is prime and 5 is not divisible by 37).

200

Compute 3¹²⁶² (mod 127)

9 

300

Compute 6⁶⁰⁰⁶ + 4⁴⁰⁰⁴ (mod 17)

9​​​​

400

How many primes p are there such that 101^p+1 is divisible by p?

3 (prime factors of 102)

500

An integer N is selected at random in the range 0 < N < 2021. What is the probability that the remainder when N¹⁶ is divided by 5 is 1?

4/5. N¹⁶ = (N⁴)⁴, so by FLT, N¹⁶ ≡ 1 (mod 5) unless N is divisible by 5. A fifth of all possible N are divisible by 5, so the probability is 4/5. 

Mixed

100

What is the smallest positive solution to x≡1 (mod 4) and x≡3 (mod 5)?

13

200

Find the smallest x > 0 such that x ≡ 2 (mod 3), x ≡ 1 (mod 4), and x ≡ 3 (mod 5).

53

300

Find x if x ≡ 1 (mod 2), x ≡ 2 (mod 3), and x ≡ 4 (mod 5)

x ≡ 29 (mod 30)

400

Solve 2^x ≡ 3 (mod 11) 

x ≡ 8 (mod 10)

500

Solve x ≡ 1 (mod 2), x² ≡ 4 (mod 3), and x³ ≡ 3 (mod 5)

x ≡ 7 (mod 30)