Elementary Number Theory Flashcards
Integers and divisibility, the Euclidean algorithm, prime numbers and prime factorisation.
Congruences
Let n be any positive integer. If a,b∈Z, then we say that a is congruent to b modulo n, and write a≡b mod n, or a≡_n b, if a and b leave the same remainder upon division by n, or equivalently, if a-b is divisible by n. (If necessary to see this, note that if a-b=kn and a=qn+r, then b=a-kn=((q-k)n+r.) The number n is sometimes called the base.
≡_n is an equivalence relation on Z.
Congruences to the same base n can be added and multiplied together: specifically, if a≡_n b and c≡_n d, then a+c≡_n b+d and ac≡_n bd. Also if ac≡_n bc and gcd(c,n) = 1, then a≡_n b.
The ring of integers mod n
Let Z_n={0,1,2,…,n-1} ,the set of n possible remainders of an integer upon division by n, and define operations of ‘addition mod n’ and multiplication mod n on Z_n by letting a+_n b be the remainder of a+b upon division by n, and a∙_n b be the remainder of ab upon division by n. Then (Z_n,+_n,∙_n) is called the ring of integers modulo n. [A ring is an algebraic structure with two binary operations].
|Z_n |=n for all n > 0.
Chinese Remainder Theorem
If the positive integers n_1,n_2,…,n_k are pairwise coprime (that is, gcd(n_i,n_j) = 1 for 1 i≤j≤k), then for every k-tuple (r_1 r_2,…,rk) of integers such that 0≤r_i<n_i for 1≤i≤k, there exists an integer a such that a≡r_i mod n_i for 1≤i≤k. (In other words, every conceivable sequence of k remainders is achievable.)
Commutativity of Z_n
The operations +_n and ∙_n are commutative on Z_n, that is, a+_n b = b+_n a and a∙_n b=b∙_n a for all a,b∈Z_n.
Associativity of Z_n
Also the operations +_n and n are associative on Zn, that is, (a+_n b)+_n c = a+_n (b+_n c) and (a ∙_n b)∙_n c = a ∙_n (b ∙_n c) for all a,b∈Z_n.
Identity of Z_n
In Z_n we call 0 an identity element for addition, because a+_n 0 =a= 0+_n a for all a∈Z_n. Similarly, 1 is an identity element for multiplication, because b∙_n 1=b =1∙_n b for all b∈Z_n.
Additive Inverse of Z_n
For every element a∈Z_n there is an additive inverse b∈Z_n, such that a+_n b=0=b+_n a, namely b=n-a.
Multiplicative Inverse of Z_n
The inverse property does not always hold for multiplication. If a,b∈Z_n and a∙_n b=1=b∙_n a, then we say that b is a multiplicative inverse for a (and vice versa), but it is not always true that every element of Z_n has a multiplicative inverse. For one thing, if n > 0 then 0 has no multiplicative inverse because 0∙_n b=0=1 for all b∈Z_n. Similarly, 2 has no multiplicative inverse in Z_6, since 2∙_6 b∈{0,2,4} for every b∈Z_6. On the other hand, in Z_7 every element other than 0 has a multiplicative inverse: 1=1∙_7 1=2∙_7 4=3∙_7 5=6∙_7 6 in Z_7, and then also 1=4 ∙_7 2=5∙_7 3 in Z_7, by commutativity.
If n is prime then every on-zero element of Z_n has a multiplicative inverse, but the same never holds when n is composite (not prime)
Units mod n
An element of Z_n that has a multiplicative inverse in Z_n is called a unit in Z_n, or a unit modulo n. The set of all units in Z_n is denoted by U(n).
If a∈Z_n is a unit in Z_n, then its multiplicative inverse in Z_n is unique.
Let k∈Z_n. Then k is a unit mod n if and only if gcd(k,n) = 1.
If p is an odd prime, then the only square roots of 1 in Z_p are 1 and p-1.
Wilson’s Theorem
Let n be an integer greater than 1. Then the product of all the non-zero elements of Z_n is congruent to n-1 mod n if and only if n is prime.
Eulers ϕ-Function
For each positive integer n, let ϕ(n) =|{k∈Z_n | gcd(k,n) = 1}| , which therefore means the number of units mod n (that is, ϕ(n) = U(n)).
ϕ(1) = 1 because U(1) = 0.
(p) = p-1 for each prime p (because every non-zero element of Z_p is a unit)
If p is a prime then ϕ(p^e )=p^e-p^((e-1) )=p^((e-1) ) (p-1)=p^e (1-1/p) for every positive integer e
Coprime Theorem
If the positive integers m and n are coprime, then ϕ(mn) =ϕ(m)ϕ(n).
Let n be any positive integer, with prime-power factorisation n = p_1^e1 p_2^e2…p_k^ek . Then ϕ(n)=ϕ(p_1^e1 )ϕ(p_2^e2 )…ϕ(p_k^ek )=p_1^e1 (1-1/p_1 ) p_2^e2 (1-1/p_2 )…p_k^ek (1-1/p_k )=n(1-1/p_1 )(1-1/p_2 )…(1-1/p_2 ).
Fermats Little Theorem
If p is prime, then a^p≡a mod p for every integer a, and a^(p-1)≡1 mod p for every integer a coprime to p.
Euler’s Theorem
If gcd(a,n) = 1 then a^ϕ(n) ≡1 mod n.
If p and q are distinct primes, then a^(((p-1)(q-1)) )≡1 mod pq whenever gcd(a,pq) = 1.
Cryptography
Typically, a message is converted from a given language (such as English) into a sequence of numbers (e.g. by converting A to 01, B to 02, C to 03, …and Z to 26, then breaking up that sequence into sub-sequences of short length, and encrypting those into a different form that is not easy to decode, before sending them. Then the recipient decrypts the received message and converts it back to one in the original language.
The RSA Method of Cryptography
Here we take n = pq where p and q are two distinct large prime numbers.
Encryption of a numerical sequences is achieved by using an encryption exponent e, to encode s as the remainder of the integer s^e modulo n, and similarly, decryption of a numerical sequence s is achieved by using a decryption exponent d, to decode s as the remainder of the integer s^d modulo n.
Thus we have an encryption function E given by E(s)≡s^e mod n, and a decryption function D given by D(s)≡s^d modulo n. These functions are created so that D(E(s)) ≡s mod n for all suitable s.
s^ed≡s^(ed-1) s≡s^kϕ(n) s≡(s^ϕ(n) )^k s≡1^k s≡s mod n, provided that s is coprime to n.
Here the pair (n,e) is the public key, made known to everyone who might send a message, while the decryption exponent d is the private key, known only to the intended receiver.
