Determine whether ##125## is a unit in ##\mathbb{Z_471}##

[chwala]

TL;DR

Allow me to post the screen shot of what the text has indicated as the steps, ...which i cannot follow fully as they have talked of back-substitution.

This is the question,

I understand the concept, in $\mathbb{Z_n}$ an element is a is a unit if and only if gcd( a,n) =1.
My understanding of backwards substitution,

...
i have using Euclidean algorithm,

$471 = 3⋅121 + 108$
$121 = 1⋅108 + 13$
$108 =8⋅13+4$
$13=3⋅4+1$
$4=4⋅1+0$

using back-substitution,

$1=13-3⋅4$
$1=(121-1⋅108)-3(108-8⋅13)$
...
$1= 121-(471-3⋅121)-3⋅471+9⋅121+24⋅121-24(471-3⋅121$
$1=121-471+3⋅121-3⋅471+9⋅121+24⋅121-24⋅471+72⋅121$
$1=109⋅121 - 28.471$
$1=109⋅121 \mod (471)$
$121^{-1}= 109 \mod (471)$

Thus, the multiplicative inverse of 121 mod 471 is 109.

I want to understand the approach that the text used. Hence, my post. Cheers.

 

[Gavran]

The back-substitution in the context of the Euclidean algorithm is:
1=9-4⋅2,
2=29-3⋅9,
1=9-4⋅(29-3⋅9)=-4⋅29+13⋅9,
9=96-3⋅29,
1=-4⋅29+13⋅(96-3⋅29)=13⋅96-43⋅29,
29=125-1⋅96,
1=13⋅96-43⋅(125-1⋅96)=-43⋅125+56⋅96,
96=471-3⋅125,
1=-43⋅125+56⋅(471-3⋅125)=56⋅471-211⋅125=260⋅125.

 

[Gavran]

i have using Euclidean algorithm,

$471 = 3⋅121 + 108$
$121 = 1⋅108 + 13$
$108 =8⋅13+4$
$13=3⋅4+1$
$4=4⋅1+0$

using back-substitution,

$1=13-3⋅4$
$=(121-1⋅108)-3(108-8⋅13)$
...
$= 121-(471-3⋅121)-3⋅471+9⋅121+24⋅121-24(471-3⋅121$
$=121-471+3⋅121-3⋅471+9⋅121+24⋅121-24⋅471+72⋅121$
$=109⋅121 - 28.471$

Although you have not used the standard step-by-step approach, your solution is also correct.

 

[chwala]

Thks @Gavran ,I will check on your approach...