modulo moment

Question 1

congruent modulo n:

Answer 1

a and b are congruent modulo n (a==b mod n) if n divides a-b

Question 2

modulo equivalence classes:

Answer 2

[r], where 0<=r<=n-1 are the remainders of some integer n, set of all these remainders is Zn

Question 3

unit:

Answer 3

an element [a] in Zn is a unit if there exists [b] such that [a][b]=[b][a]=[1], so [a] has a multiplicative inverse, Un is the set of all units in Zn

Question 4

units and gcds:

Answer 4

[a] is a unit in Zn iff gcd(a,n)=1

Question 5

Un the group:

Answer 5

abelian under multiplication modulo n w/ identity element [1]

Question 6

wilson’s theorem:

Answer 6

a positive integer p is prime iff (p-1)!== -1 mod p

Question 7

euler’s function:

Answer 7

ϕ(n) is the no. of positive integers a <= n w/ gcd(a,n)=1

Question 8

ϕ(p^m):

Answer 8

(p-1)p^(m-1)

Question 9

ϕ(mn):

Answer 9

ϕ(m)ϕ(n) when m,n coprime

Question 10

ϕ(n), n w/ prime factorisation p1^m1…pk^mk:

Answer 10

ϕ(n)=ϕ(p1^m1)…ϕ(pk^mk)=p1^(m1-1)(p1-1)…pk^(mk-1)(pk-1)

Question 11

(d|n)Σϕ(d):

Answer 11

n

Question 12

euler’s theorem:

Answer 12

a,n positive integers w/ gcd(a,n)=1, then a^(ϕ(n))==1 mod n

Question 13

fermat’s little theorem:

Answer 13

p prime, a an integer not divisible by p, a^(p-1)==1 mod p