Quiz 4 Lemmas/Theorems

Question 1

Chinese Remainder Theorem Formula

Answer 1

x ≅ ((n^-1 modm)na + (m^-1 modn)mb) (modmn)

Question 2

What does phi(p) do?

Answer 2

If GCD(m,n) = 1, then phi(mn) = phi(m)phi(n). Furthermore, if p is a prime number then phi(p) = p-1, phi(p^2) = p^2 - p,….., phi(p^n) = p^n - p^(n-1)

Question 3

What is (mod mn), if m and n are relatively prime?

Answer 3

If m and n are relatively prime and x^2 ≅ a(modmn), then those solutions are in 1-to-1 correspondence with (u,v) where u^2 ≅ a(mod m) and v^2 ≅ a(mod n).

Question 4

Hensel Lifting

Answer 4

If p is an odd prime, where we know x^2 ≅ a(mod p), then we can solve for x^2 ≅ a(mod p^2)

Question 5

For PHI(p), when is ‘a’ a quadratic residue?

Answer 5

‘a’ is a quadratic residue if there exists an ‘x’ in PHI(p) such that x^2 ≅ a(mod p)

Question 6

Legendre Symbol

Answer 6

Legendre symbol of a/p is:
1. 1 if a is a quadratic residue (mod p)
2. 0 if p|a
3. -1 if a is a quadratic non-residue (mod p)

Question 7

a-partners

Answer 7

If a,x,y are elements of PHI(p), then x,y are a-partners if xy ≅ a(mod p)

Question 8

Wilsons Theorem

Answer 8

If p is an odd prime then (p-1)! ≅ -1(mod p)

Question 9

Euler’s Criterion

Answer 9

1. a is a qr (mod p) iff a^(p-1)/2 ≅ 1(mod p)
2. a is a qnr (mod p) iff a^(p-1)/2 ≅ -1(mod p)

Question 10

Quadratic Reciprocity