11.

12.

13.

14.

15.

16.

18.

19.

20.
21.
22.

28.

154396

2 D 12645

Let a and b be integers, not both zero. Then prove that a and b are relatively prime if and only if

there exist integers a and f such that 1=aa+ fb.
Prove that if a| and }|c, and (a, b) = 1, then ab|c.

Prove that every integer n >2 has a prime factor.

Let f, denote the n‘ Fermat number. Then prove that f, =f; _, —2f,_, + 2, where n 21.

Express ged (28, 12) as a linear combination of 28 and 12.

(10 x 3 = 30 marks)
Section B

Answer atleast five questions.

Each question carries 6 marks.

All questions can be attended.
Overall ceiling 30.

Show that the propositions p v (¢ Ar) and (pv q) A(pv r) are logically equivalent.
Show that theassertion “All primes are odd” is false.

Let } be an integer > 2. Suppose db + lintegers are randomly selected. Prove that the difference of
two of them is divisible by b.

Ifpisaprime and p|a,q,...a,, then prove that p|a; at for some i, where 1
Show that 11 x 14n + 1 is acomposite number.
There are infinitely many primes of the form 4n + 3.

Show that 2!!218_ 1 is not divisible by 11.
Prove that if n >1 and gcd (a, n) = 1,then a”) =1 (mod n).

(5 x 6 = 30 marks)

154396