Download IITian Academy App for accessing Online Mock Tests and More..
Question
Use the Euclidean Algorithm to show that \(275\) and \(378\) are relatively prime.
Find the general solution to the diophantine equation \(275x + 378y = 1\) .
Answer/Explanation
Markscheme
\(378 = 1 \times 275 + 103\) A1
\(275 = 2 \times 103 + 69\) A1
\(103 = 1 \times 69 + 34\) A1
\(69 = 2 \times 34 + 1\) A1
showing that gcd \( = 1\) , i.e. relatively prime. R1
[5 marks]
Working backwards,
\(1 = 69 – 2 \times (103 – 69)\) (M1)
\( = 3 \times 69 – 2 \times 103\) (A1)
\( = 3 \times (275 – 2 \times 103) – 2 \times 103\)
\( = 3 \times 275 – 8 \times 103\) (A1)
\( = 3 \times 275 – 8 \times (378 – 275)\)
\( = 11 \times 275 – 8 \times 378\) (A1)
A solution is \(x = 11\) , \(y = – 8\) (A1)
The general solution is \(x = 11 + 378n\) , \(y = – 8 – 275n\) where \(n \in \mathbb{Z}\) M1A1 N6
[7 marks]
Question
Find the general solution to the Diophantine equation \(3x + 5y = 7\).
Find the values of \(x\) and \(y\) satisfying the equation for which \(x\) has the smallest positive integer value greater than \(50\).
Answer/Explanation
Markscheme
by any method including trial and error or the Euclidean algorithm, a specific solution is, for example, \(x = 4,{\text{ }}y = – 1\) (A1)(A1)
\(3(4) + 5( – 1) = 7\;\;\;\)(equation i)
\(3x + 5y = 7\;\;\;\)(equation ii)
equation ii – equation i: \(3(x – 4) + 5(y + 1) = 0\)
\(\frac{{4 – x}}{5} = \frac{{y + 1}}{3} = N\) (M1)
\(x = 4 – 5N\) A1
\(y = 3N – 1\) A1
smallest positive integer \( > 50\) occurs when \(N = – 10\) (M1)
\(x = 54,{\text{ }}y = – 31\) A1
Question
Consider the Diophantine equation \(7x – 5y = 1,{\text{ }}x,{\text{ }}y \in \mathbb{Z}\).
Find the general solution to this equation.
Hence find the solution with minimum positive value of \(xy\).
Find the solution satisfying \(xy = 2014\).
Answer/Explanation
Markscheme
one solution is \(x = – 2,{\text{ }}y = – 3{\text{ }}\left( {{\text{or }}(3,{\text{ }}4)} \right)\) (A1)
the general solution is
\(x = – 2 + 5N,{\text{ }}y = – 3 + 7N{\text{ }}({\text{or }}x = 3 + 5M,{\text{ }}y = 4 + 7M)\) M1A1
[3 marks]
a listing of small values of the product (M1)
\( \Rightarrow x = – 2,{\text{ }}y = – 3\) (the least positive value of \(xy\) is 6) A1
[2 marks]
use of “table” or otherwise to solve
\(35{N^2} – 29N + 6 = 2014{\text{ }}({\text{or }}35{M^2} + 41M + 12 = 2014)\) (M1)
obtain \(N = 8{\text{ }}({\text{or }}M = 7)\) (A1)
\(x = 38,{\text{ }}y = 53\) A1
[3 marks]