Number Theory Flashcards
(18 cards)
State Euclid’s algorithm
Suppose that a, b are integers. Then there are integers m, n such that am + bn = (a, b).
Define a unit
A number with a multiplicative inverse.
Define an irreducible number
A number which is not a unit and has no non-trivial factors.
Define a prime number
A number p is a prime if it is not a unit and p|ab implies that either p|a or p|b.
Define mod
Let q > 1 be an integer. Then we write a ≡ b(mod q) if and only if q divides a - b.
Define the multiplicative group of residues mod q
(Z/qZ)^x = {x + qZ ∈ Z/qZ: (x, q)=1}
State the Chinese Remainder Theorem
Suppose that q1, q2, …, qk are pairwise coprime positive integers and that a1, …, ak are integers. Then there is an integer x such that x ≡ ai (mod qi) for i = 1, 2, …, k. Moreover, x is unique (mod q1…qk).
State Fermat’s Little Theorem
Let p be a prime, and suppose that a is not a multiple of p. Then a^(p-1) ≡ 1 (mod p).
State Wilson’s Theorem
Let p be an odd prime. Then (p-1)! ≡ –1 (mod p).
Define Euler’s ϕ-function
ϕ(n) is the number of positive integers less than or equal to n which are also coprime to n.
State Fermat-Euler’s Theorem
Suppose that q is a positive integer and that a is coprime to q. Then a^ϕ(q) ≡ 1 (mod q).
Define the order of an integer
Let q be a positive integer such that an integer a is coprime to q. Then the order of a mod q is defined to be the smallest positive integer n such that an ≡ 1(mod q).
Define a primitive root
Given a prime p, an element g ∈ (Z/pZ)x is called a primitive root if it has ordp(g) = p-1.
Define a quadratic residue
Given an odd prime p, a ∈ (Z/pZ)x is a quadratic residue modulo p if a and p are coprime and there is an integer x such that x^2 ≡ a (mod p).
Define a quadratic non-residue
Given an odd prime p, a ∈ (Z/pZ)x is a quadratic non-residue modulo p if a and p are coprime and there are no integers x such that x^2 ≡ a (mod p).
State Euler’s criterion
Let p be an odd prime and suppose that a ∈ (Z/pZ)x. Then a(p-1)/2 ≡ 1 (mod p) if a is a quadratic residue and -1 (mod p) if a is a quadratic nonresidue.
Define Legendre’s symbol
Suppose that p is a prime, and let a ∈ Z. We define the Legendre symbol (a/b) to equal 1 if (a, p) = 1 and a (mod p) is a quadratic residue modulo p, -1 if (a, p) = 1 and a (mod p) is a quadratic nonresidue modulo p, and 0 if p|a.
State Gauss’ lemma
Let p be an odd prime and let I ⊂ (Z/pZ)x be a set such that (Z/pZ)x is the disjoint union of I and -I. Let a be an integer coprime to p. Then (a/p) = (-1)^t , where t = #{j ∈ I : aj ∈ -I}.
