MATH 470 Lecture 2

From Notes
Jump to navigation Jump to search

« previous | Thursday, January 17, 2013 | next »


Fundamental Theorem of Arithmatic

Any n∈ℤ can be written as n=∏i=1kpiai for pairwise distinct primes p1,…,pk and a1,…,ak∈ℤ


Corollary

GCD(p1a1…pkak,p1b1…p1min⁡(a1,b1)…pkmin⁡(ak,bk)


Corollary

If a,x,n∈ℤ with GCD(a,n) = 1 and n∣(ax),then<math>n∣x


Extended Euclidean Algorithm

Input: a,b∈Z
Output: g:=GCD(a,b) and (x,y)∈ℤ2 with ax+by=g

  1. Form matrix [1001ab]
  2. Use elementary column operations (only allowing divisions by ≠ 1) to reduce to [uxvy0g]
  3. You have your answers g, x, and y

Example

Solve 173x=3(mod256)

Rewrite as 173x+256y=3. Find x and y such that 173x+256y=1

[1001173256]⟶[1−10117383]→[3−1−21783]→[3−34−22376]→[37−34−252316]→[37−256−2517310]→[−25637173−2501]

Therefore, all of the following are true:

  • 173(37)+256(−25)=1
  • 173⋅37=1(mod256)
  • 1173=37(mod256)


1173173x=3(1173)(mod256)=3⋅37(mod256)=111(mod256)

Complexity: Lame's Theorem

Number of column operations needed is ≤ 5 × number of digits in smaller number

Theorem on Congruences

Given any a,b,n∈ℤ, the congruence ax=b(modn) has exactly g:=GCD(a,n) solutions when g∣b and no solutions otherwise

Example

27x=18(mod45) has solutions {4,9,14,19,24,29,34,39,44}.

How would we have known?

  1. find GCD(a,n) via Extended Euclidean Algorithm (GCD(27,45)=9; 27(2)+45(−1)=9)
  2. divide out equation by g (3x=2(mod5))
  3. solve equation above (x=4)
  4. solutions are: {x,x+ng,…,x+(g−1)ng}


Proof

First note that g∤b implies no solutions.

Indeed ax=b(modn) implies ax+ny=b for some x,y∈ℤ.

g∣(ax+ny), so g∤b leads to a contradiction.

For example, 2x=1(mod8) cannot be solved since 2x+8y is even and 1 is odd.


Let's assume g∣b

if g∣{a,b,n}, and x is any solution to ax=b(modn), so is x+i(ng) for any i∈{0,…,g−1}


Indeed, a(x+i(ng))≡ax+i(ang)≡b+in(ag)≡b(modn)


Moreover, ng,2ng,…,(g−1)ng are clearly distinct mod n

It's enough to consider g=1

To conclude, ax≡b(modn)⟺ax+ny=b has only one solution.

Now suppose if there are two solutions (x1,y1) and (x2,y2), then we get

ax1+ny1=bax2+ny2=ba(x1−x2)+n(y1−y2)=0

GCD(a,n)=1, so since n divides the RHS, it also divides the LHS

Therefore, n∣(x1−x2)⟹x1≡x2(modn)

Q.E.D.


CAS Stuff

Maple

> (* Matrices *)
> M := matrix([[a,b,c],[d,e,f],[g,h,i]]);


Sage

sage: # Affine Ciphers == of the form: f(x) = a*x + b (mod 26)
sage: A = AffineCryptosystem(AlphabeticStrings());
sage: P = A.encoding("Hey! How's it going?");
  => HEYHOWSITGOING
sage: a,b = (9,13);
sage: cipher = A.enciphering(a,b,P);
  => YXVYJDTHCPJHAP


Solving Linear Systems

(mod an integer)


{2x+3y=1(mod26)7x+14y=2(mod26)

Put into an augmented matrix

[2317142]

First operation would be to subtract 7/2 times the first row from the second row... TROUBLE! What's 1/2 mod 26? (undefined)

2 options

  1. Do gaussian elimination without dividing by two (similar to E.E.A.)
  2. Use adjoints


First Option

[2317142]→[15−10−73]

x+5y=−1(mod26)−7y=3(mod26)

We can invert -1/7 mod 26:

−17=−15=11(mod26)

y=3⋅11=7(mod26)x=−36=16(mod26)

Second Option

Cramer's rule

(x,y)=(|13214||23714|,|2172||23714|)


We only have to invert 7, which is relatively prime to 26, so it is possible.

Theorem

You can solve Ax=b(modn) for any k×k matrix of integers A and any k×1 vector of integers b when GCD(|A|,n)=1