Unknown

1.6. Basic Number Theory and Modular Arithmetic 33

Explain where the numbers in the top row come from. Show that

the numbers in the bottom row can be obtained successively by

following the scheme

*. 21

v w uw+v.

Explain the relevance of the scheme. Finally, show how the table

can be used to find numbers 21, yr, x2, y2, x3, y3 to satisfy

(b) Find integers x and y to satisfy

(i) 3 = 121: + 21y

(ii) 9 = 12x + 21y

(iii) 6 = 24x + 66y

(iv) gcd(20119,34782) = 20119x + 34782~.

This exercise illustrates the general result: Let a and b be two

integers whose greatest common divisor is g. Show that there

exists integers x and y such that g = ux + by.

The set {uc + by : x, y E Z} is precisely the set of all multiples

of the greatest common divisor of a and b.

(c) Using the general result enunciated in (b), show that every com-

mon divisor of a pair of integers divides the greatest common

divisor.

3. (a) Let p be a prime and a be any integer. Show that a is a multiple
   of p if and only if the greatest common divisor of p and a is not
   
   
   1. (b) Show that, if a is not a multiple of the prime p, then there exist
      integers z and y for which 1 = ux + py.
      (c) Prove that, if a and b are any integers, and if the prime p is a
      divisor of the product ub, then either p\u or plb.
      (d) Let n 1 2 be a positive integer. Show that there are prime
      numbers pl , ~2,... ,pk and positive exponents el, e2,... , ek such
      that
      n=p;lpT...pp.
   
   
   
   

Show that this representation is unique up to the order of the

prime power factors.

(e) Give the representation described in (e) for the numbers 418,

1606, 20119 and 34782.