Lecture 12

May 29

Binomial theorem

states that: , where binomial(n,i) denotes the binomial coefficient, n choose i, equal to n!/(i!*(n-i)!), and n! denotes n factorial = 1*2*3*...*n , with 0!=1 .

Proof: by induction on n. for n=1 the left hand side is (x+y)^1=x+y and the right hand side is

sum(binomial(1,i)*x^(1-i)*y^i,i=0..1)

=binomial(1,0)*x^(1-0)*y^0+binomial(1,1)*x^(1-1)*y^1

=1*x*1+1*1*y=x+y .

So the theorem is true for n=1. Assume the theorem is true for n=k, and show that it is also true for n=k+1.

The left hand side at n=k+1 is:

(x+y)^(k+1)

=(x+y)^k*(x+y)^1

=(x+y)*(x+y)^k , Now use our assumption that it holds for n=k.

=(x+y)*sum(binomial(k,i)*x^(k-i)*y^i,i=0..k) .

=x*sum(binomial(k,i)*x^(k-i)*y^i,i=0..k)+y*sum(binomial(k,i)*x^(k-i)*y^i,i=0..k)

=sum(binomial(k,i)*x^(k-i+1)*y^i,i=0..k)+sum(binomial(k,i)*x^(k-i)*y^(i+1),i=0..k)

=x^(k+1)+sum(binomial(k,i)*x^(k-i+1)*y^i,i=1..k)+sum(binomial(k,i)*x^(k-i)*y^(i+1),i=0..k-1)+y^(k+1)

=x^(k+1)+sum(binomial(k,j+1)*x^(k-(j+1)+1)*y^(j+1),j=0..k-1) + sum(binomial(k,i)*x^(k-i)*y^(i+1),i=0..k-1)+y^(k+1)

=x^(k+1)+sum(binomial(k,i+1)*x^(k-i)*y^(i+1),i=0..k-1)+sum(binomial(k,i)*x^(k-i)*y^(i+1),i=0..k-1)+y^(k+1)

=x^(k+1)+sum((binomial(k,i+1)+binomial(k,i))*x^(k-i)*y^(i+1),i=0..k-1)+y^(k+1), Now use Pascal's triangle rule to add the 2 binomial coefficients and replace them with a single binomial coefficient from the next row.

=x^(k+1)+sum(binomial(k+1,i+1)*x^(k-i)*y^(i+1),i=0..k-1)+y^(k+1)

=x^(k+1)+sum(binomial(k+1,j)*x^(k-(j-1))*y^((j-1)+1),j=1..k)+y^(k+1)

=x^(k+1)+sum(binomial(k+1,i)*x^(k-i+1)*y^i,i=1..k)+y^(k+1)

=sum(binomial(k+1,i)*x^(k+1-i)*y^i,i=0..k+1)

= the right hand side at n=k+1 . Therefore by the inductive asumption the binomial theorem is true.

Note: it also works for n=0 since (x+y)^0=1 and binomial(0,0)*x^0*y^0=1*1*1=1

Example:

> expand((x+y)^5);

>

Fermat's Theorem

a^p=a (mod p) for p a prime.

Proof: for a=0 0^p=0 , so it is true for a=0. For a=1 , 1^p=1 so it is also true for a=1. What about for a=2? We will use the binomial theorem to expand (1+1)^p:

(1+1)^p

=sum(binomial(p,i)*1^(p-i)*1^i,i=0..p)

=sum(binomial(p,i),i=0..p)

=1+sum(binomial(p,i),i=1..p-1)+1 .

Now we will look at the binomial coefficient binomial(p,i) modulo p . We have binomial(p,i)=p!/i!/(p-i)! . We have that 1<=i<=p-1 because we are only looking at the middle binomial coefficients. also 1<=p-i<=p-1 . Since p is a prime number it has no proper divisors . So p!/i!/(p-i)!=p*((p-1)!/i!/(p-i)!) Every factor in the denominator is less than p and the binomial coefficients are integers, so the denominator factors i! and (p-i)! must divide (p-1)! and not divide into p. Therefore every middle binomial coefficient is a multiple of p, so they would reduce to 0 modulo p . Therefore

(1+1)^p (mod p)

=1 + sum(0,i=1..p=1) +1 (mod p)

=2 (mod p).

Therefore Fermat's theorem is true for a=2 . Now we will use induction to proof it true for all positive integers a.

We have just shown that it is true for a=1. Now assume it is true for a=k, We will show it is true for a=k+1.

We have:

(k+1)^p (mod p)

=sum(binomial(p,i)*k^(p-i)*1^i,i=0..p) (mod p)

=k^p + sum(binomial(p,i)*k^(p-i),i=1..p-1) + 1^p (mod p)

=k^p + 1 (mod p), because all the middle binomial coefficients are multiples of p , so are congruent to 0 modulo p.

=k+1 (mod p) , by our inductive assumption k^p=k (mod p)

Therefore Fermat's theorem is true for all a>=0 and all primes p.

Note: it also holds for negative values of a.

Examples:

> poly1 := expand((x+y)^7);

> poly2 := poly1 mod 7;

> for i from 0 to 14 do 'modp'(i^7,7)=modp(i^7,7) od;

reciprocal's modulo m

How do we compute 1/a (mod m) ?

We want to find an x such that x=1/a (mod m) . Multiply this equation by a to find a*x=1 (mod m). This is just a special case of the linear equation a*x+b=0 (mod m) for b=-1. We can solve this by applying the extended Euclidean algorithm to a and m. giving us s and t such that s*a+t*m=gcd(a,m). Now we need to assume that a and m are relatively prime so that gcd(a,m)=1 . Therefore s*a+t*m=1 . Now reduce this equation modulo m, noting that t*m=0 (mod m), and we see that s*a=1 (mod m) . so x=1/a=s .

Examples:

> 1/3 mod 10;

> 1/15 mod 33;

Error, the modular inverse does not exist

> 1/6 mod 19;

Fermat's theorem alternate version

states that a^(p-1)=1 (mod p) for all prime's p, and all a relatively prime to p.

Proof: from Fermat's theorem (other version) a^p=a (mod p) for all a , and all prime p. If gcd(a,p)=1 then x exists such that x=1/a (mod p) by the above reciprocal theorem. Just multiply by x to find

x*a^p=x*a (mod p), which becomes

(x*a)*a^(p-1)= 1 (mod p), whch becomes

a^(p-1)=1 (mod p) .

Examples: 2^6 (mod 7)=64 (mod 7)=(7*9+1) (mod 7)=1 (mod 7)

> seq(power(i,6) mod 7,i=1..6);

> power(17,36) mod 37;

Euler's theorem

Consider the powers of some number reduced modulo some other number

Examples:

> seq(power(3,i) mod 11,i=1..22);

> seq(power(5,i) mod 11,i=1..22);

> seq(power(7,i) mod 11,i=1..22);

What if the base is not relatively prime to the modulus?

> seq(power(8,i) mod 10,i=1..10);

> seq(power(12,i) mod 21, i=1..21);

We see that all the powers are multiples of the gcd(base,modulus) .

order

If gcd(a,m)=1 then the powers of a modulo m must eventually repeat because we only have m distinct congruence classes. Suppose that a^i=a^j (mod m) . Since gcd(a,m)=1 there exists x such that x=1/a (mod m) or x*a=1 (mod m). Just multiply both sides by x^i and we find x^i*a^i=x^i*a^j (mod m) . This reduces to 1=a^(j-i) mod m. Therefore some power of a=1 (mod m). We call the smallest positve integer exponent e the order of a modulo m, if gcd(a,m)=1 and a^e=1 (mod m) and e is the smallest such positive integer satisfying the equation a^f=1 (mod m) for an unknown positive integer f. We write this as order(a,m)=e.

Examples:

from the above calculations we see that order(3,11)=5, order(5,11)=5, order(7,11)=10.

> with(numtheory):

> order(3,11);

> order(1,9);

> order(2,11);

> order(10,11);

> order(6,10);

> order(3,16);

> order(7,99);

Check

> seq(power(7,i) mod 99,i=1..30);

Compute all values of order for a fixed modulus m

> seq(order(i,11),i=1..10);

> phi(11);

> seq(order(i,35),i=1..34);

> phi(35);

Notice that the set of possible value's for the order with respect to a fixed modulus m are some of the divisors of Euler's .

Euler's theorem states that (mod m) if gcd(a,m)=1 .

Proof: Let {x[1],x[2],...x[k]} be the set of least residues modulo m , where all of thenm are relatively prime to m. Therefore gcd(x[i],m)=1 for i=1,...k . Note there are such least residues. So k= . Now multiply each of them by a and reduce modulo m,and we obtain the set {a*x[1] (mod m),a*x[2] (mod m), ... , a*x[k] (mod m)} . Can there be any duplicates in this set? Aswer: No. Why? Suppose that a*x[i]=a*x[j] (mod m). Since gcd(a,m)=1 we know that a has a reciprocal b such that b*a=1 (mod m). Just multiply this equation by b to find that (b*a)*x[i]=(b*a)*x[j] (mod m). This simplifys to x[i]=x[j] (mod m). We assumed that the x[i]'s were distinct , therefore the set {a*x[1],a*x[2],...,a*x[k]} is also the set of least residues modulo m, possibly in some other order. Just multiply the elements in each set together to find that:

x[1]*x[2]*...*x[k] (mod m) = (a*x[1])*(a*x[2])*...*(a*x[k]) (mod m).

=a^k*x[1]*x[2]*...*x[k] (mod m). Let y[i] be the reciprocal of x[i] modulo m. It exists since gcd(x[i],m)=1. Just multiply our equation by y[1]*y[2]*...*y[k] to cancel out all the x[i]'s on both sides. We are left with:

1=a^k (mod m) . Recall k= , so Euler's theorem has been proved.

Examples:

> power(2,10) mod 11;

> phi(15);

> power(7,8) mod 15;

Wilson's theorem

If p is prime then (p-1)!=-1 (mod p)

Proof: Since p is prime =p-1 . The set of least residues that are relatively prime to p must be the set {1,2,...,p-1}. Since gcd(i,p)=1 for 1<=i<=p-1, every element i in the set would have a reciprocal j that is also in the set. Which just pair up the numbers in the product 1*2*3...*(p-1)=(p-1)! in such a way that i*j occur together so they may be reduced to 1 modulo p. We will be left with those numbers that are there own reciprocal such as 1 and -1. Note:

(-1)*(-1)=1. So -1 is its own reciprocal. If a number is its own reciprocal then it must satisfy the equation x=1/x (mod p) . This may be multiplied by x to yield x^2=1 (mod p) . Thiis can be expressed as (x^2-1)=0 (mod p) . We know that x^2-1=(x-1)*(x+1) . So we have (x-1)*(x+1)=0 (mod p) . This means that p | (x-1)(x+1) , and since p is a prime we know that this implies that p | (x-1) or p | (x+1) . If p | (x-1) and 1<=x<=p-1, then x=1 is the only choice. If p | (x+1) and x>=1 then the only choice is x=p-1 . Note p-1=-1 (mod p). So the only least absolute residues are x=1 and x=-1. So now our product (p-1)!=(i*1/i)*(j*1/j)*...(k*1/k)*1*(-1)=-1 (mod p).

Examples:

4! (mod 5) = 1*2*3*4=24 (mod 5)=4 (mod 5)=-1 (mod 5)

> mods(10!,11);

> mods(12!,13);

reducing rational numbers modulo m

Let a be an integer and b be a natural number, then a/b is a rational number. How do we compute (a/b) (mod m) ?

We just write this as a*(1/b) (mod m) . Then we compute the reciprocal of b , call it z, then z*b=1 (mod m). This assumes that gcd(b,m)=1 otherwise b would not have a reciprocal. Therefore a/b (mod m) =a*z (mod 10)

Examples:

> a := -19: b := 12: m := 625:

> z := 1/b mod m;

> ans := a*z mod m;

Check:

> mods(ans*b,m);

Note: we can just find the answer directly by:

> a/b mod m;

rational number reconstruction

How can we reverse the above process? That is we are given a residue c=363 and the modulus m=625. How can be find the rational number a/b such that a/b (mod m) = c ? Since there are an infinite number of rational numbers, the solution is not unique. For example: 41/7 (mod 625)=363

> 41/7 mod 625;

But 41 is a big mumber, so maybe we could make the solution unique by restricting the numerators and the denominators of our answers. Suppose we also impose a numerator bound NB and a denominator bound DB, such that our solution n/d is such that -NB<=n<=NB and -DB<=d<=DB . Let us derive some equations on the size of the bounds that would guarantee a unique solution. Let n1/d1 and n2/d2 we two solutions then:

n1/d1=n2/d2 (mod m). Cross multiply to find:

n1*d2=n2*d1 (mod m).

n1*d2-n2*d1=0 (mod m) . Write as an equation over the integers.

n1*d2-n2*d1=k*m. Maximize the left hand side.

NB*DB-(-NB)*DB=2*NB*DB , We want this number small, so it is not a multiple of m. Therefore we must choose our bounds such that 2*NB*DB<m if we are going to find a unique solution. So for our exmaple, we could choose NB=20 and DB=15 then 2*20*15=600<625=m. Note this eliminates our other solution 41/7 , because 41>20. Still we wonder how can we find a/b without doing a brute force search. Remember the extended Euclidean algorithm. We will apply it to c and m, stopping with the i'th remiander and i'th multiplier y[i] are both small enough.

Recall the in place version of the algorithm , where we don't wait until the last remainder is 0, before starting to back-solve, but we back solve as we go.

We have r[-1]=m, r[0]=c to start with. The the first division step gives us

r[-1]=r[0]*q[1]+r[1]. We back-solve this for r[1]=r[-1]-q[1]*r[0] = 1*m-q[1]*c . Therefore x[1]=1 and y[1]=-q[1]. Now look at thid equation modulo m and the 1*m term goes to 0 and we are left with r[1]=-q[1]*c (mod m). We rewrite this as r[1]/(-q[1])=c (mod m) . We now have our first rational approximation to our answer.

If abs(r[1])<=NB and abs(q[1])<=DB then we are finished and we output a=r[1], b=-q[1] as our answer. If not then we do another step of the extended Euclidean algorithm to find:

r[0]=r[1]*q[2]+r[2]. We back-solve this for r[2]=r[0]-r[1]*q[2]=r[0]-(r[-1]-q[1]*r[0])*q[2] =(1+q[1]*q[2]) * r[0] -q[2]*r[-1] = -q[2]*m+(1+q[1]*q[2])*c . This can be rewritten as x[2]*m+y[2]*c=r[2] , if we define x[2]=-q[2], and y[2]=1+q[1]*q[2] . Now we reduce this (mod m) to find r[2]/y[2]=c (mod m).

Once again if abs(r[2])<=NB and (y[2])<=DB then we are finished. Otherwise we repeat this process until we find a solution or until we reach the last remainder=0, and we stop and output no solution possible.

Example: find a/b=363 (mod 625) with abs(a)<=20 and abs(b)<=15.

625=363*1+262, => 262=625-1*363, 262>20 , so continue

363=262*1+101, => 101=363-262=363-(625-363)=-1*625+2*363 , 101>20 , so continue

262=101*2+60, => 60=262-2*101=(625-363)-2*(-1*625+2*363)=3*625-5*363, 60>20

101=60*1+41, => 41=101-60=-625+2*363-3*625+5*363=-4*625+7*363 , 41>20

60=41*1+19 , => 19=60-41=3*625-5*363+4*625-7*363=7*625-12*363 , 19<=20, and abs(-12)<=15 so stop.

reduce mod 625 to find 19=-12*363 (mod 625) . Therefore 363 (mod 625)=19/(-12)=-19/12 .

Maple has a procedure for doing this, called iratrecon

> c := 363: m := 625: NB := 20: DB := 15:

> readlib(iratrecon);

> iratrecon(c,m,NB,DB,'n','d');

> n;

> d;

> ans := n/d;

What does the body of iratrecon look like?

> interface(verboseproc=2);

> eval(iratrecon);

> debug(iratrecon);

> iratrecon(c,m,NB,DB,'n','d');

{--> enter iratrecon, args = 363, 625, 20, 15, n, d

<-- exit iratrecon (now at top level) = true}

>