Question

Q 9. In this question, you must clearly set out your working, describing your process with full English sentences. (a) Using Euclid's Algorithm 14.13, show that ged(25, 33) = 1, and hence find integers x, y E Z such that x · 25+ y: 33 = 1. Clearly state the values of x and y. (b) By the Multiplicative Inverse Theorem 14.22, it follows from (a) that 25 has a multiplicative inverse, 25(-1), in Z33. Calculate 25(-1) using your answer to (a). Check your answer: a check must be included for full marks.

Answer 1

Solution: Q 9.

(D)

Using Euclid's Algorithm we have,

33 = 1 x 25 +8...... (1)

25 = 3 x 8 + 1...... (2)

$\small 8=8\times 1+0$

The last non-zero remainder is $\small 1$ and therefore $\small \mathrm{gcd}\left ( 25,33 \right )=1.$

From $\small \left ( 1 \right )$ we have,

$\small 8=33-1\times 25......\left ( 3 \right )$

From  $\small \left ( 2 \right )$ we get

$\small 1=25-3\times 8$

$\small \therefore 1=25-3\times \left ( 33-25 \right )$, from

3

$\small \therefore 1=25-3\times 33+3\times 25$

$\small \therefore 1=4\times 25-3\times 33$

$\small \therefore x=4,\: \: \: \: y=-3$

$\small \left ( b \right )$

From , we have

(D)

$\small \mathrm{gcd}\left ( 25,33 \right )=1.$

$\small \therefore 25$ has a multiplicative inverse in $\small \mathbb{Z}_{33}$

Also, $\small 1=4\times 25-3\times 33$

The value of $\small x$ ( the coefficient of $\small 25$ ) is $\small 4$ , so  $\small 25^{\left ( -1 \right )}=4$ .

Check:  $\small 25\times 4=100=3\times 33+1\equiv 1\left ( \mathrm{mod}\: 33 \right )$