Lecture 10

May 24

Congruences

Recall the definition of congruence: We say x is congruent to y modulo m and we write this as x=y (mod m) . We call m the modulus. This means that m divides (y-x) , where x and y are integers and m is a non-zero integer. Also recall that the congruence relation is an equivalence relation. This means that we can partition the set of integers into pairwise mutually disjoint, equivalence classes, of sets of integers.

Example: Suppose the modulus m=4 , then what are the equivalence classes? How many equivalence classes are there? How many integers are in each equivalence class? Note the equivalence classes under the congruence relation are also called congruence classes

They are S1={...-7,-3,1,5,9,...} , S2={...,-10,-6,-2,2,6,10,...}, S3={-9,-5,-1,3,7,11,...} and S4={...,-8,-4,0,4,8,...}.

S1={4*k+1 : k }. S2={4*k+2 : k }. S3={4*k+3 : k }. S4={4*k : k }. There are exactly 4 equivalence classes , which is the same number as the modulus m=4 . Each equivalence class contains an infinite number of integers.

Definition: A congruence class modulo m is the set of all integers congruent to a fixed integer k, where m is a natural number.

Definition: A complete residue system modulo m is a set of integers such that exactly one integer in the set is in each congruence class.

Examples: {0,1,2,3} is a compete residue system modulo 4. So is {5,-8,6,11} . But {1,2,3,-1} is not, because 3 and -1 are in the same congruence class.

Solving polynomial equations modulo m. Let P(x) be a polynomial with integer coefficients. If r is a root of P(x) modulo m , then P(r)=0 (mod m).

Example: Find some solutions to P(x)=0 (mod 3) where P(x)=x^2-1 . We have P(1)=1^2-1=1-1=0 , so 1 is a root. P(2)=2^2-1=4-1=3= 0 (mod 3) , so 2 is a root. P(3)=3^2-1=8=2 (mod 3), so 3 is not a root, P(4)=4^2-1=16-1=15=0 (mod 3), so 4 is a root. P(5)=5^2-1=25-1=24=0 (mod 3) .

Theorem: If r is a root of P(x)=0 (mod m) then r+k*m is also a root, where k is an arbitrary integer.

Proof: Let P(x)=a[n]*x^n+a[n-1]*x^(n-1)+...+a[1]*x+a[0]. P(r+k*m)=a[n]*(r+k*m)^n+a[n-1]*(r+k*m)^(n-1)+...+a[0]

= a[n]*(r^n+n*r^(n-1)*(k*m)+...+(k*m)^n)+a[n-1]*(r^(n-1)+(n-1)*r^(n-2)*(k*m)+...+(k*m)^(n-1))+...+a[1]*(r+(k*m))+a[0]

=a[n]*r^n+a[n-1]*r^(n-1)+a[0] (mod m) since all the other terms contain a multiple of m, so they are congruent to 0. The sum is just P(r) (mod m), but we assumed that P(r)=0 (mod m). Therefore P(r+k*m)=0 (mod m).

The above theorem means that we only need to give one solution from each congruence class.

Definition: A complete solution to the polynomial equation P(x)=0 (mod m) is a set of solutions , such that each member of the set belongs to exactly one congruence class:

Example: x^2-1=0 (mod 3) has the complete solution {1,5} , since 1 and 5 belong to different congruence classes modulo 3.

Definition: The least complete solution to the polynomial equation P(x)=0 (mod m) is the set of solutions , such that each member of the set belongs to exactly one congruence class, and each solution is in the range 0,1,...m-1.

Example: x^2-1 (mod 3) has the least complete solution {1,2} .

Definition: The least absolute complete solution to the polynomial equation P(x)=0 (mod m) is the set of solutions , such that each member of the set belongs to exactly one congruence class, and each solution is in the range -m/2+1...-2,-1,0,1,2,...m/2 for m a positive even number, or in the range -(m-1)/2...,-2,-1,0,1,2,...(m-1)/2 for m a positive odd number.

Example: x^2-1 (mod 3) has the least absolute complete solution {1,-1} .

Algorithm to find the least complete solution to a polynomial congruence

Our first algotithm will use a brute force search over all the least residues as in the following Maple procedure.

> #read com_sol;

> com_sol := proc (p, x::name, m::posint) local k, i, r, s; if not type(p,polynom(integer,x)) then ERROR(`the first argument must be a polynomaial in the secon argument`) fi; k := 0; for i from 0 to m-1 do r := `mod`(eval(p,x = i),m); if r = 0 then k := k+1; s[k] := i fi od; {seq(s[i],i = 1 .. k)} end;

> com_sol(x^2-1,x,3);

Compare this with Maple's msolve

> msolve(x^2-1,3);

> p := sort(randpoly(x,degree=6,dense,coeffs=rand(0..9)));

> com_sol(p,x,10);

> msolve(p,10);

> com_sol(x^2+2*x+3,x,6);

> com_sol(x^2+1,x,3);

> com_sol(2*x+3,x,6);

> com_sol(2*x+4,x,6);

The linear polynomial congruence equation

How do we solve a*x+b=0 (mod m) for x ? We could use our brute force search algorithm, but we are looking for a faster algorithm. This equation means that m | (a*x+b) or k*m=a*x+b for some integer k . We rearrange this as a*x+m*(-k)=-b as a linear equation in the two variables x and k. We already know how to solve such equations. We use the extended Euclidean algorithm with inputs a and m . This gives us g=gcd(a,m) and two integers s and t such that a*s+m*t=g . Since g divides both a and m , let A=a/g and M=m/g . If g does not divide -b then there are no solutions. If g divides -b with quotient q=-b/g then we just divide our equation by g to obtain (a/g)*s+(m/g)*t=1 , which is A*s+M*t=1 Then we multiply this by q to obtain A*(s*q)+M*(t*q)=q . Now we have reduced our modulus from m to M=m/g , so our solution is x=s*q (mod M). A complete solution modulo m is then obtained by adding back the first g multiples of m/g=M . This is x={(s*q+j*M) (mod m): j=0,1,2,...g-1} .

Examples:

Find the least complete solution to 8*x+5=0 (mod 12) . The gcd(8,12)=4 and 4 does not divide 5 so there are no solutions. Check with our procrdure com_sol

> com_sol(8*x+5,x,12);

Find the least complete solution to 21*x+33=0 (mod 51). First we compute the gcd(21,51) by the Euclidean algorithm by hand.

21=51*0+21

51=21*2+9

21=9*2+3

9=3*3+0.

Therefore gcd(21,51)=3 and -33/3=-11 so there is a solution. We now back solve the remainder sequence to obtain

3=21-9*2

=21-2*(51-2*21)=5*21-2*51 .

This extended Euclidean algorithm equation is 21*5+51*(-2)=3 . We divide this by 3 to obtain 7*5+17*(-2)=1 . Then we multiply this by -11 to obtain 7*(-11*5)+17*((-2)*(-11))=-11 which becomes 7*(-55)+17*(22)=-11 . Our reduced modulus is 51/3=17 . Our solution x=-55 (mod 17) or

x=13 (mod 17) . We convert this back to our original modulus by adding back the first g=3 multiples of M=17 . This gives the least complete solution set as x={13,13+17,13+2*17} which is x={13,30,47} . Now check with com_sol.

> com_sol(21*x+33,x,51);

We can create a procedure for finding the solution to the linear equation a*x+b=0 mod m and the reduced modulus M. Here it is:

> #read one_lin_sol;

> one_lin_sol := proc (a, b, m) local g, s, t, q, r, M; description `Find the solution to a*x+b=0 (mod m)`, `input is a,b,m`, `output is MOD(x,M)`, `where x is the solution`, `and M is the reduced modulus`; g := igcdex(a,m,'s','t'); q := iquo(-b,g,'r'); if r <> 0 then {} else M := iquo(m,g); t := modp(s*q,M); MOD(t,M) fi end;

> one_lin_sol(21,33,51);

> one_lin_sol(21,34,51);

We can also write a procedure to find the least complete solution set to the linear congruence equation a*x+b=0 (mod m) . It is:

> #read com_lin_sol;

> com_lin_sol := proc (a, b, m) local g, s, t, q, r, M, i; description `Find the least complete solution to a*x+b=0 (mod m)`; g := igcdex(a,m,'s','t'); q := iquo(-b,g,'r'); if r <> 0 then {} else M := iquo(m,g); t := modp(s*q,M); {seq(t+i*M,i = 0 .. g-1)} fi end;

> com_lin_sol(21,33,51);