Introduction to number theory
Section A
1. (a) Use Fermat’s Method to factorize 1147. [5]
(b) Euclid’s algorithm applied to two numbers a and b computed the quotients q1 = 3,
q2 = 3, q3 = 3, q4 = 3, q5 = 3 (in this order) and their greatest common divisor
gcd(a, b) = 3. Compute a and b. [5]
2. Using the extended version of Euclid’s algorithm, find a solution to the following Dio-
phantine linear equation.
77x + 91y + 143z = 2 [10]
3. Find all solutions for the following pair of simultaneous congruences.
262x ≡ 3 mod 807
3x ≡ 2 mod 5 [10]
4. Show that the equation
2×3 + 7y3 = 4 has no solution in integers. [10]
5. (a) Derive the continued fraction of √7. [5]
(b) Find the value of β, given its continued fraction expression β = [1, ̄7], i.e., a0 = 1
and ai = 7 for all i ∈ {1, 2, . . .}. [5]
