Congruent Modulo n



Modulo Arithmetic

Problem:

If we line up the students in this class in 2 rows, there is one student left. If we line up them in 3 rows, there are two left. If we line up them in 5 rows, there are 3 left. How many number of students in this class?

Definition. Given a, b are integers and n is a positive integer,

a[pic]b (mod n) , or a and b are congruent modulo n,

if n|(a-b).

Example. 3 [pic]0 (mod 3), 4[pic] 1 (mod 3), 5 [pic]2 (mod 3), 6[pic] 0 (mod 3), -1[pic] 2 (mod 3),

-2[pic] 1 (mod 3), …

Now, we can collect all integers that are congruent in the same set, called the congruent class, as defined in the following:

Definition. The set of integers congruent to r (mod n) is called the congruence class of r (mod n), is the set

[r]={ r + kn | k[pic] Z}

The collection of [0], [1], .., [n-1] is denoted by Zn.

Definition. The Integers modulo n, or Zn , is defined as

Zn ={[0], [1], [2], …, [n-1]}

Theorem. The following are equivalent:

i) a[pic]b (mod n)

ii) [a]=[b]

iii) There are exactly n congruence classes (mod n), i.e.,

[0], [1], [2], …, [n-1]

The modulo arithmetic + and * do not depend on the representation, as in the following:

Theorem. If a, b, c, and d are integers, a[pic]b (mod n) and c[pic]d (mod n)

i) a +c[pic]b +d (mod n)

ii) ac[pic]bd (mod n)

Definition. If [r] and [s] are congruence classes (mod n), then

[r]+[s]=[r+s]

[r][s]=[rs]

Example. In Z4 ={[0], [1], [2], [3]}

[1]+[1]=[2], [1]+[2]=[3], [1]+[3]=[4]=[0], [2]+[2]=[0], [2]+[3]=[1], [3]+[3]=[2]

[2][2]=[4]=[0], [2][3]=[6]=[2], [3][3]=[9]=[1]

Definition. A non-zero element [r] [pic]Zn is called a zero-divisor if there exists a non-zero element [s] [pic]Zn such that [r][s]=[0].

Definition. A non-zero element [r] [pic]Zn is called a unit if there exists a non-zero element [s] [pic]Zn such that [r][s]=[1]. [s] is called a multiplicative inverse of [r], or [r]-1.

Example. In Z4,

[2] is a zero-divisor and [3] is a unit. The multiplicative inverse of [3] is itself.

Example.

What is [15]-1 (mod 2)?

Solution:

Since 15*1 (mod 2)= 1 (mod 2), [15]-1 =[1].

Theorem. For a congruence class [r] [pic]Zn, the following are equivalent:

i) gcd (m, n)=1

ii) [m] has a multiplicative inverse.

iii) [m] is not a zero-divisor in Zn.

Example.

In Z4, n=4, m=3, gcd(3,4)=1. Hence [3] has a multiplicative inverse, which is itself.

Corollary.

Every non-zero [r] in Zn has a multiplicative inverse if and only if n is a prime,.

Example.

In Z5, n=5, [1]-1 = [1], [2]-1 = [3], [3]-1 = [2], [4]-1 = [4].

Definition. A function f has a period of r (positive integer) if f(x+r)=f(x), for every x.

Example.

In Z4, calculate the Fibonacci sequence.

[0], [1], [1], [2], [3], [1], [0], [1], …

The period is 6.

Theorem. (The Chinese Remainder Theorem)

Assume that a1, a2, …, am are integers, and n1, n2, …, nm are positive integers such that gcd (ni, nj)=1 if i [pic] j (ni, nj are called relatively prime).

Then the system equation

X[pic] a1 (mod n1)

X[pic] a2 (mod n2)

…

X[pic] am (mod nm)

Has a unique solution X modulo N=n1 *n2 *…*nm

Proof:

Let Ni = [pic][pic] = [pic]. Obviously, Ni [pic] 0 (mod nj), where i=1, 2, …, m and i[pic]j

Then gcd (Ni, ni)=1. Hence there is a multiplicative inverse Ri (=Ni-1) of Ni (mod ni).

Let X= [pic]. Since X= [pic][pic] ai (mod ni), X is the unique solution.

Example.

If we line up the students in this class in 2 rows, there is one student left. If we line up them in 3 rows, there are two left. If we line up them in 5 rows, there are 3 left. How many number of students in this class?

That is, to solve the system equation

X[pic] 1 (mod 2)

X[pic] 2 (mod 3)

X[pic] 3 (mod 5)

Solution:

m=3, a1=1, a2=2, a3=3, n1 =2, n2=3, n3=5. N= n1*n2* n3 =30

N1 = n2* n3 = 15, R1 =1 (mod 2)

N2 = n1* n3 = 10, R1 =1 (mod 3)

N3 = n1* n2 = 6, R1 =1 (mod 5)

X= [pic]=15*1*1+10*1*2+6*1*3=53 (mod 30)=23 (mod 30)

Applications.

A. DNA Model (Z4)

The genetic code in DNA of organism is in the form of double helix, each consisting of a sequence of nucleotides: T(Thymine), A(Adenine), C(Cytosine) and G(Guanine). The double helix is governed by Chargaff’s Rules: T pairs with A and G pairs with C.

If we set T=0, A=2, G=1 and C=3, then every helix can interchange to another strand of helix by using modulo arithmetic (adding 2) in Z4.

For example, one strand of the human TSH- [pic]gene has the genetic code as

GGTCACCACAGCATCTGCTCACCAATGCAAAGTAAG

This can be represented in by Z4 as

1103233232132030130323322013222102221

After adding 2 (mod 4) respectively, the other helix code is

3321011010310212312101100231000320003

The genetic code is

CCAGTGGTGTCGTAGACGAGTGGTTACGTTTCATTTC

B. Public Key Encryption/Decryption (RSA Algorithm)

The public key encryption is used by a sender to transmit a secret key. The sender first encrypts the key (called a plain text T, e.g., a positive integer from the key’s ASCII code) using a public key (displayed from a web site) and transmit it (called a cipher text C) to the other person. The receiver will use the corresponding private key to decode the message and know the secret key. Then the receiver will use the secret key to communicate with the sender. The idea is that even people know the public key, it is supposed very hard to find the corresponding private key to decode it. One such algorithm is called RSA algorithm (developed in 1976 by Rivest, Shamir and Adleman at MIT) is described as follows: (PQ, E) is the public key)

1) Choose 2 different prime numbers P and Q. (In practice, each has 200 digits).

2) Choose an odd number E such that gcd (E, (P-1)(Q-1)) = 1

3) By the theorem above, find a multiplicative inverse of E (mod (P-1)(Q-1)), called D (the private key). That is ED [pic]1 (mod (P-1)(Q-1))

Assume that ED=1+m(P-1)(Q-1), where m is an integer

4) The cipher text C is created by C=TE (mod PQ).

5) To decipher C, the receiver performs

CD (mod PQ)= TED (mod PQ)= (T Tm(P-1)(Q-1)) (mod PQ)

If gcd(T,P)=1, then by Fermat theorem, Tm(P-1) [pic] 1 (mod P), or Tm(P-1)(Q-1) [pic] 1 (mod P)

If gcd(T,Q)=1, then by Fermat theorem, Tm(Q-1) [pic] 1 (mod Q), or Tm(P-1)(Q-1) [pic] 1 (mod Q)

Therefore, if gcd(T,P)=1 and gcd(T,Q)=1, then by Chinese Reminder Theorem that Tm(P-1)(Q-1) [pic] 1 (mod PQ), or CD (mod PQ)=T (mod PQ)

The receiver can recover the original plain text T.

Note:

1) Choose 2 large primes P and Q:

i) The Fermat’s Little Theorem (Fermat’s primes p)

If p is prime and a is an integer not divisible by p, then

ap-1 [pic]1 (mod p).

Example.

Let a=2, p=5. 24 = 16 [pic]1 (mod 5)

However, this does not guarantee that if an-1 [pic]1 (mod n), then n is a prime. This composite number n is called a Carmichael number (or a pseudo-prime)

Example.

Let a=2, n=561=3*11*17

Then 2560=(22) 280 [pic]1280 (mod 3) [pic]1 (mod 3) [pic]1 (mod 561).

n=561 is not a prime.

ii) The Euclid’s primes

Let Nn = p1 * p2 * …* pn +1, where p1, p2, …, pn are the first n primes in order). Then N1, N2, N3, N4, N5, N11, N75, N171, and N172 are primes. No other Nn are primes for 1 [pic]n[pic] 200.

iii) The Mersenne primes

If p is a prime, then Mp =2p -1 is called a Mersenne number.

Lucas Theorem. Mp is prime if and only if Mp divides S, where

S0 = 4, S1 = 42 -2=14, S2 = 142 -2, …, Sk = Sk-12 -2.

iv) The Gaussian primes

2k

If a prime has the form 2 +1, it is a Gaussian prime. Only when k=0, 1, 2, 3, 4, it is prime.

2) Choose an odd integer E that is not divisible by (P-1)(Q-1)

3) D can be found using the Euclidean algorithm and Extended Euclidean algorithm as follows:

Procedure moduloMultiplicativeInverse (given a, b are positive integers and a [pic]b, modulo n)

// stores all quotient in array q[0], q[1], … and stores as count the number of steps used in Euclidean //Algorithm

// The following is the Euclidean Algorithm

x=a

y=b

i=0

While y [pic] 0

q[i]=x div y

r=x mod y

x=y

y=r

i++

count=i

// the following is the extended Euclidean algorithm

xprev=0

x=1

for i=0 to count-2

xnew=( xprev-x*q[i]) mod n

xprev=x

x=xnew

// make x non-negative

while x ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download