Unknown

34 1. Fundamentals

4. (a) Let two positive integers m and n be written out as a product of
   prime powers. Express the greatest common divisor u and least
   common multiple v of m and n as a product of the powers of
   the primes involved in representing m and n.
   (b) Show that mn = uv.
   (c) Show that v divides every common multiple of m and n.


5. Let m E N and a, b E Z. We say that a E b (mod m) (read: “a is
   congruent to b modulo m”) if and only if mlu - b.

(a) Show that a - b (mod m) if and only if a and b have the same

remainder upon division by m.

(b) If a E b and c - d (mod m), show that a + c - b + d (mod m)

and UC E bd (mod m). Explain how we take account of these

facts every time we add up a column of figures or multiply two

large numbers using paper and pencil.

(c) Show that if p is any polynomial with integer coefficients, and if

a E b (mod m), then p(u) E p(b) (mod m).

6. Let m E N, and a, b E Z. Consider the problem of solving the follow-
   ing congruence
   ux E b (modm).
   A solution is any number k for which uk - b is divisible by m.

(a) Show that 7 is a solution of the congruence 4x z 3 (mod 5).

Find all other solutions of this congruence.

(b) Find all solutons of the congruences

(i) 4x z 3 (mod 6)

(ii) 4x - 2 (mod 6).

Cc) ;;;ngg;f3 c^4 a, m). Show that, if ux E b (mod m) has a solution,

(d) Conversely, show that if g = gcd(u,m) and glb, then the con-

gruence ux q b (mod m) has a solution.

(e) We say that the solution of a congruence ux 5 b (mod m) is

unique module m, or, simply, unique if the difference between

any solutions is divisible by m. In other words, the requirement

is that au E au G b (mod m) implies u E’V (mod m).

Show that the solution of the congruence is unique if and only

if gcd(u,m) = 1.

(f) Show that, if p is a prime, and a is not a multiple of p, then

there is exactly one value of x satisfying

uxrl(modp) and l<zlp-1.