Which of the following pairs of integers (x,y) satisfies 2947x+1113y=(2947,1113)?

Divide 2947 by 1113: 2947=2×1113+721 Divide 1113 by 721: 1113=1×721+392 Divide 721 by 392: 721=1×392+329 Divide 392 by 329: 392=1×329+63 Divide 329 by 63: 329=5×63+14 Divide 63 by 14: 63=4×14+7 Divide 14 by 7: the remainder is now zero: 14=2×7+0 Rearrange the last non-zero remainder line: 7=63-4×14 Substitute 14=329-5×63 from the line above: 7=(-4)×329+21×63 Substitute 63=392-1×329 from the line above: 7=21×392+(-25)×329 Substitute 329=721-1×392 from the line above: 7=(-25)×721+46×392 Substitute 392=1113-1×721 from the line above: 7=46×1113+(-71)×721 Substitute 721=2947-2×1113 from the line above: 7=(-71)×2947+188×1113 Test the pair in the equation: 2947×(-71)+1113×188=7 Select the correct pair: 2947×(-71)+1113×188=(2947,1113)=7 Answer: (-71,188)

In the Euclidean algorithm the integers a and b (with b>0) are written as a=bq+r where 0≤ r<b. Which of the following is equal to (a,b) for all such a and b?

Write down the division line: a=bq+r, 0≤ r<b Let d be a common divisor of a and b: d a and d b Deduce that d divides r: r=a-bq d r Now let e be a common divisor of b and r: e b and e r Deduce that e divides a: a=bq+r e a Conclude that the greatest common divisors agree: (a,b)=(b,r) Test the false option (a,r): a=16, b=6: q=2, r=4,(16,6)=24=(16,4) Test the false option (q,r): a=100, b=7: q=14, r=2,(100,7)=12=(14,2) Test the false option (a,q): a=15, b=6: q=2, r=3,(15,6)=31=(15,2) Test the false option (b,q): a=15, b=6:(15,6)=32=(6,2) Note that this is what makes the algorithm work: (a,b)=(b,r_1)=(r_1,r_2)=·s Note that the remainder is an integer combination of a and b: r=a-bq Note that the same argument justifies Bezout's identity: (a,b)=ax+by Note where the algorithm stops: (r_k,0)=r_k Check the invariance on a concrete pair: (84,30)=6=(30,24) Recall the division algorithm: a=bq+r, 0≤ r<b Select the expression equal to (a,b): (a,b)=(b,r) Answer: (b,r)

Hard Further Maths Number theory Questions

Challenging, exam-style Further Maths Number theory questions with worked solutions. Stretch yourself on the hardest extended-euclidean-algorithm, bezout-identity, linear-congruence, modular-arithmetic problems.

extended-euclidean-algorithmbezout-identitylinear-congruencemodular-arithmeticlinear-diophantine-equationfermats-little-theorem

Further Maths34 questionsStep-by-step solutions

Question 1

9 markschallenging

Which of the following is the least residue of

7^{2024}

modulo

1000

Show worked solution

Worked solution

Write the exponent as a sum of powers of $2$
$2024=1024+512+256+128+64+32+8$
Repeated squaring produces exactly these powers of $7$ .
Square to reach the exponent $2$
$7^{2}\equiv7^{2}=49\equiv49\pmod{1000}$
Reducing modulo $1000$ after every squaring keeps the arithmetic small.
Square to reach the exponent $4$
$7^{4}\equiv49^{2}=2401\equiv401\pmod{1000}$
Reducing modulo $1000$ after every squaring keeps the arithmetic small.
Square to reach the exponent $8$
$7^{8}\equiv401^{2}=160801\equiv801\pmod{1000}$
Reducing modulo $1000$ after every squaring keeps the arithmetic small.
Square to reach the exponent $16$
$7^{16}\equiv801^{2}=641601\equiv601\pmod{1000}$
Reducing modulo $1000$ after every squaring keeps the arithmetic small.
Square to reach the exponent $32$
$7^{32}\equiv601^{2}=361201\equiv201\pmod{1000}$
Reducing modulo $1000$ after every squaring keeps the arithmetic small.
Square to reach the exponent $64$
$7^{64}\equiv201^{2}=40401\equiv401\pmod{1000}$
Reducing modulo $1000$ after every squaring keeps the arithmetic small.
Square to reach the exponent $128$
$7^{128}\equiv401^{2}=160801\equiv801\pmod{1000}$
Reducing modulo $1000$ after every squaring keeps the arithmetic small.
Square to reach the exponent $256$
$7^{256}\equiv801^{2}=641601\equiv601\pmod{1000}$
Reducing modulo $1000$ after every squaring keeps the arithmetic small.
Square to reach the exponent $512$
$7^{512}\equiv601^{2}=361201\equiv201\pmod{1000}$
Reducing modulo $1000$ after every squaring keeps the arithmetic small.
Square to reach the exponent $1024$
$7^{1024}\equiv201^{2}=40401\equiv401\pmod{1000}$
Reducing modulo $1000$ after every squaring keeps the arithmetic small.
Multiply in the factor $7^{32}$
$801\times201=161001\equiv1\pmod{1000}$
The exponent $2024$ is the sum $8+32$ , so these are exactly the powers that must be multiplied together.
Multiply in the factor $7^{64}$
$1\times401=401\equiv401\pmod{1000}$
The exponent $2024$ is the sum $8+32+64$ , so these are exactly the powers that must be multiplied together.
Multiply in the factor $7^{128}$
$401\times801=321201\equiv201\pmod{1000}$
The exponent $2024$ is the sum $8+32+64+128$ , so these are exactly the powers that must be multiplied together.
Multiply in the factor $7^{256}$
$201\times601=120801\equiv801\pmod{1000}$
The exponent $2024$ is the sum $8+32+64+128+256$ , so these are exactly the powers that must be multiplied together.
Multiply in the factor $7^{512}$
$801\times201=161001\equiv1\pmod{1000}$
The exponent $2024$ is the sum $8+32+64+128+256+512$ , so these are exactly the powers that must be multiplied together.
Select the least residue
$7^{2024}\equiv401\pmod{1000}$
This is the remainder when the power is divided by $1000$ .

Answer

401

Question 2

9 markschallenging

Which of the following pairs of integers

\left(x,y\right)

satisfies

2947x+1113y=\gcd\left(2947,1113\right)

Show worked solution

Worked solution

Divide $2947$ by $1113$
$2947=2\times1113+721$
The remainder $721$ is smaller than the divisor $1113$ , so the algorithm continues with the pair $\left(1113,721\right)$ .
Divide $1113$ by $721$
$1113=1\times721+392$
The remainder $392$ is smaller than the divisor $721$ , so the algorithm continues with the pair $\left(721,392\right)$ .
Divide $721$ by $392$
$721=1\times392+329$
The remainder $329$ is smaller than the divisor $392$ , so the algorithm continues with the pair $\left(392,329\right)$ .
Divide $392$ by $329$
$392=1\times329+63$
The remainder $63$ is smaller than the divisor $329$ , so the algorithm continues with the pair $\left(329,63\right)$ .
Divide $329$ by $63$
$329=5\times63+14$
The remainder $14$ is smaller than the divisor $63$ , so the algorithm continues with the pair $\left(63,14\right)$ .
Divide $63$ by $14$
$63=4\times14+7$
The remainder $7$ is smaller than the divisor $14$ , so the algorithm continues with the pair $\left(14,7\right)$ .
Divide $14$ by $7$ : the remainder is now zero
$14=2\times7+0$
The last non-zero remainder is $7$ , so the algorithm stops and $\gcd\left(2947,1113\right)=7$ .
Rearrange the last non-zero remainder line
$7=63-4\times14$
The last non-zero remainder is the gcd, so this line is the starting point of the back-substitution.
Substitute $14=329-5\times63$ from the line above
$7=\left(-4\right)\times329+21\times63$
Each substitution climbs one line up the algorithm, keeping the gcd written as an integer combination of two of the numbers.
Substitute $63=392-1\times329$ from the line above
$7=21\times392+\left(-25\right)\times329$
Each substitution climbs one line up the algorithm, keeping the gcd written as an integer combination of two of the numbers.
Substitute $329=721-1\times392$ from the line above
$7=\left(-25\right)\times721+46\times392$
Each substitution climbs one line up the algorithm, keeping the gcd written as an integer combination of two of the numbers.
Substitute $392=1113-1\times721$ from the line above
$7=46\times1113+\left(-71\right)\times721$
Each substitution climbs one line up the algorithm, keeping the gcd written as an integer combination of two of the numbers.
Substitute $721=2947-2\times1113$ from the line above
$7=\left(-71\right)\times2947+188\times1113$
Each substitution climbs one line up the algorithm, keeping the gcd written as an integer combination of two of the numbers.
Test the pair in the equation
$2947\times\left(-71\right)+1113\times188=7$
The pair produced by the back-substitution satisfies Bezout's identity.
Select the correct pair
$2947\times\left(-71\right)+1113\times188=\gcd\left(2947,1113\right)=7$
Only this pair reproduces the gcd.

Answer

\left(-71,188\right)

Question 3

9 markschallenging

In the Euclidean algorithm the integers

a

and

b

(with

b>0

) are written as

a=bq+r

where

0\le r<b

. Which of the following is equal to

\gcd\left(a,b\right)

for all such

a

and

b

Show worked solution

Worked solution

Write down the division line
$a=bq+r,\qquad 0\le r<b$
This is the single line the Euclidean algorithm repeats.
Let $d$ be a common divisor of $a$ and $b$
$d\mid a\ \text{and}\ d\mid b$
The aim is to show that $d$ is then a common divisor of $b$ and $r$ .
Deduce that $d$ divides $r$
$r=a-bq\ \Rightarrow\ d\mid r$
A divisor of $a$ and of $b$ divides any integer combination of them.
Now let $e$ be a common divisor of $b$ and $r$
$e\mid b\ \text{and}\ e\mid r$
The converse direction is proved in exactly the same way.
Deduce that $e$ divides $a$
$a=bq+r\ \Rightarrow\ e\mid a$
So the two pairs have exactly the same common divisors.
Conclude that the greatest common divisors agree
$\gcd\left(a,b\right)=\gcd\left(b,r\right)$
Identical sets of common divisors have the same greatest element.
Test the false option $\gcd\left(a,r\right)$
$a=16,\ b=6:\quad q=2,\ r=4,\quad\gcd\left(16,6\right)=2\ne4=\gcd\left(16,4\right)$
One counterexample is enough to kill that option.
Test the false option $\gcd\left(q,r\right)$
$a=100,\ b=7:\quad q=14,\ r=2,\quad\gcd\left(100,7\right)=1\ne2=\gcd\left(14,2\right)$
The quotient carries no information about the common divisors.
Test the false option $\gcd\left(a,q\right)$
$a=15,\ b=6:\quad q=2,\ r=3,\quad\gcd\left(15,6\right)=3\ne1=\gcd\left(15,2\right)$
The quotient is not tied to the common divisors at all.
Test the false option $\gcd\left(b,q\right)$
$a=15,\ b=6:\quad\gcd\left(15,6\right)=3\ne2=\gcd\left(6,2\right)$
The same counterexample disposes of this option.
Note that this is what makes the algorithm work
$\gcd\left(a,b\right)=\gcd\left(b,r_{1}\right)=\gcd\left(r_{1},r_{2}\right)=\cdots$
Each line replaces the pair by a strictly smaller one with the same gcd.
Note that the remainder is an integer combination of $a$ and $b$
$r=a-bq$
This is the identity that both halves of the proof above rely on.
Note that the same argument justifies Bezout's identity
$\gcd\left(a,b\right)=ax+by$
Reversing the algorithm expresses the final remainder in terms of $a$ and $b$ .
Note where the algorithm stops
$\gcd\left(r_{k},0\right)=r_{k}$
The last non-zero remainder is therefore the gcd of the original pair.
Check the invariance on a concrete pair
$\gcd\left(84,30\right)=6=\gcd\left(30,24\right)$
Here $84=2\times30+24$ , and the gcd is unchanged.
Recall the division algorithm
$a=bq+r,\qquad 0\le r<b$
For any integers $a$ and $b>0$ there are unique integers $q$ and $r$ of this form.
Select the expression equal to $\gcd\left(a,b\right)$
$\gcd\left(a,b\right)=\gcd\left(b,r\right)$
This identity is the engine of the Euclidean algorithm.

Answer

\gcd\left(b,r\right)

Question 4

9 markschallenging

Let

f(n)=5^{n}+2\times11^{n}

. In a proof by induction that

f(n)

is divisible by

3

for all positive integers

n

, which of the following is the correct simplified form of

f(k+1)-5f(k)

Show worked solution

Worked solution

State the base case
$f\left(1\right)=27=3\times9$
The result is true for $n=1$ because $3$ divides $27$ .
State the inductive hypothesis
$f\left(k\right)=3M\ \text{for some integer}\ M$
Assume the result holds for some $n=k$ ; this is what the inductive step is allowed to use.
Write down $f\left(k+1\right)$
$f\left(k+1\right)=22\times11^{k}+5\times5^{k}$
Replacing $n$ by $k+1$ is the whole of the inductive step's raw material.
Subtract $5f\left(k\right)$
$f\left(k+1\right)-5f\left(k\right)=22\times11^{k}+5\times5^{k}-5\left(2\times11^{k}+5^{k}\right)=12\times11^{k}$
This particular multiple of $f\left(k\right)$ is subtracted because it cancels the dominant term and leaves something visibly divisible by $3$ .
Rearrange to isolate $f\left(k+1\right)$
$f\left(k+1\right)=5f\left(k\right)+12\times11^{k}$
Everything now depends on $f\left(k\right)$ , which the hypothesis controls.
Substitute the inductive hypothesis
$f\left(k+1\right)=5\times3M+3\times4\times11^{k}$
The first term is a multiple of $3$ by the hypothesis, and the second is $3$ times the integer $4\times11^{k}$ .
Factorise out $3$
$f\left(k+1\right)=3\left(5M+4\times11^{k}\right)$
The bracket is an integer, so $3$ divides $f\left(k+1\right)$ .
Complete the induction
$\text{true for}\ n=k\ \Rightarrow\ \text{true for}\ n=k+1$
With the base case this proves the result for every positive integer $n$ .
Check the claim at $n=2$
$f\left(2\right)=267=3\times89$
A second value is a useful sanity check before the algebra starts.
Check the claim at $n=3$
$f\left(3\right)=2787=3\times929$
The pattern of divisibility continues.
Note the alternative congruence argument
$\text{work modulo}\ 3\ \text{throughout}$
Reducing every base modulo $3$ proves the same result without induction.
Note why a multiple of $f\left(k\right)$ is subtracted
$f\left(k+1\right)-5f\left(k\right)\ \text{must be a multiple of}\ 3$
Any expression of the form $5f\left(k\right)+3C$ is divisible by $3$ once the hypothesis is used.
Check the answer numerically at $k=2$
$f\left(3\right)-5f\left(2\right)=2787-5\times267=1452$
This agrees with the general expression at $k=2$ .
Recall the division algorithm
$a=bq+r,\qquad 0\le r<b$
For any integers $a$ and $b>0$ there are unique integers $q$ and $r$ of this form.
Recall what divisibility means
$b\mid a\iff a=bk\ \text{for some integer}\ k$
Every divisibility argument in this topic goes back to this definition.
Select the correct simplified form
$f\left(k+1\right)-5f\left(k\right)=12\times11^{k}$
This is the expression the inductive step produces.

Answer

12\times11^{k}

Question 5

9 markschallenging

Find the remainder when

3^{2024}

is divided by

100

Show worked solution

Worked solution

Square to reach the exponent $2$
$3^{2}\equiv3^{2}=9\equiv9\pmod{100}$
Reducing modulo $100$ after every squaring keeps the arithmetic small.
Square to reach the exponent $4$
$3^{4}\equiv9^{2}=81\equiv81\pmod{100}$
Reducing modulo $100$ after every squaring keeps the arithmetic small.
Square to reach the exponent $8$
$3^{8}\equiv81^{2}=6561\equiv61\pmod{100}$
Reducing modulo $100$ after every squaring keeps the arithmetic small.
Square to reach the exponent $16$
$3^{16}\equiv61^{2}=3721\equiv21\pmod{100}$
Reducing modulo $100$ after every squaring keeps the arithmetic small.
Square to reach the exponent $32$
$3^{32}\equiv21^{2}=441\equiv41\pmod{100}$
Reducing modulo $100$ after every squaring keeps the arithmetic small.
Square to reach the exponent $64$
$3^{64}\equiv41^{2}=1681\equiv81\pmod{100}$
Reducing modulo $100$ after every squaring keeps the arithmetic small.
Square to reach the exponent $128$
$3^{128}\equiv81^{2}=6561\equiv61\pmod{100}$
Reducing modulo $100$ after every squaring keeps the arithmetic small.
Square to reach the exponent $256$
$3^{256}\equiv61^{2}=3721\equiv21\pmod{100}$
Reducing modulo $100$ after every squaring keeps the arithmetic small.
Square to reach the exponent $512$
$3^{512}\equiv21^{2}=441\equiv41\pmod{100}$
Reducing modulo $100$ after every squaring keeps the arithmetic small.
Square to reach the exponent $1024$
$3^{1024}\equiv41^{2}=1681\equiv81\pmod{100}$
Reducing modulo $100$ after every squaring keeps the arithmetic small.
Multiply in the factor $3^{32}$
$61\times41=2501\equiv1\pmod{100}$
The exponent $2024$ is the sum $8+32$ , so these are exactly the powers that must be multiplied together.
Multiply in the factor $3^{64}$
$1\times81=81\equiv81\pmod{100}$
The exponent $2024$ is the sum $8+32+64$ , so these are exactly the powers that must be multiplied together.
Multiply in the factor $3^{128}$
$81\times61=4941\equiv41\pmod{100}$
The exponent $2024$ is the sum $8+32+64+128$ , so these are exactly the powers that must be multiplied together.
Multiply in the factor $3^{256}$
$41\times21=861\equiv61\pmod{100}$
The exponent $2024$ is the sum $8+32+64+128+256$ , so these are exactly the powers that must be multiplied together.
Multiply in the factor $3^{512}$
$61\times41=2501\equiv1\pmod{100}$
The exponent $2024$ is the sum $8+32+64+128+256+512$ , so these are exactly the powers that must be multiplied together.
Multiply in the factor $3^{1024}$
$1\times81=81\equiv81\pmod{100}$
The exponent $2024$ is the sum $8+32+64+128+256+512+1024$ , so these are exactly the powers that must be multiplied together.
State the remainder
$3^{2024}\equiv81\pmod{100}$
This is the remainder when $3^{2024}$ is divided by $100$ .

Answer

81

Unlock 29 more Number theory questions

Create a free account to work through every Further Maths Number theory question with instant step-by-step worked solutions, progress tracking and interactive lessons.

Full worked solutions for every question
Interactive lessons and instant feedback
Track your mastery across every topic

Create a Free Account

No card required · Free forever

More Number theory practice

Practice Questions Worked Solutions

Hard Further Maths Number theory Questions

Worked solution

Worked solution

Worked solution

Worked solution

Worked solution

Unlock 29 more Number theory questions

More Number theory practice

Related Further Pure topics