Elementary Number Theory

Question 1

Congruences

Answer 1

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.

Question 2

The ring of integers mod n

Answer 2

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.

Question 3

Chinese Remainder Theorem

Answer 3

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.)

Question 4

Commutativity of Z_n

Answer 4

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.

Question 5

Associativity of Z_n

Answer 5

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.

Question 6

Identity of Z_n

Answer 6

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.

Question 7

Additive Inverse of Z_n

Answer 7

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.

Question 8

Multiplicative Inverse of Z_n

Answer 8

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)

Question 9

Units mod n

Answer 9

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.

Question 10

Wilson’s Theorem

Answer 10

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.

Question 11

Eulers ϕ-Function

Answer 11

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

Question 12

Coprime Theorem

Answer 12

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 ).

Question 13

Fermats Little Theorem

Answer 13

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.

Question 14

Euler’s Theorem

Answer 14

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.

Question 15

Cryptography

Answer 15

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.

Question 16

The RSA Method of Cryptography

Answer 16

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.