CYG Chapter 6 Number-Theoretic Reference Problems

Basics about number theory // Useful for cryptography

1. Z_n = Z/nZ

2. Equivalence relation s~t or s equiv t (mod n) ↔ n|(s-t)

3. (Z_n,+,*) forms a commutative ring

4. Multiplicative group

5. Euler phi-function

Z_n* := {a in Z_n| gcd(a,n)=1}

If Z_n* is multiplicative abelian group then gcd(a,n)=1 iff ex inverse s of a with a*s equiv 1 (mod n)

Phi(n) = |Z_n*|

Phi(p)=p-1 for any prime p

1. If a in Z_n* then a^phi(n) equiv 1 (mod n)

2. If p is prime and (a,p)=1 then a^p-1 equiv 1 (mod p) // Fermat’s little theorem

1. (a,n) for gcd(a,n)

2. If (a,n)=1 then a and n are called relatively prime or coprime