0
$\begingroup$

I need some help solving b).

enter image description here

My approach is the following:

I solved a) as follows: a is a unit, find it's inverse using the extended eucledian algorithm.

For b). If c is not a unit, no problem, jsut apply a). If a is not a unit do the following:

Let $g = gcd(n,a)$. Thus $c = b*g*\frac{a}{g}$ and hene if we denote $\frac{a}{g}$ as e we see that $g|c$, so c is not a unit too. This alows us to calculate $\frac{c}{g}$ in $\mathbb{Z}$, which can be calculated efficiently. Moreover, I noticed using basic gcd properties, that $gcd(e, \frac{n}{g}) = 1$, so e is invertible in $\mathbb{Z}_\frac{n}{g}^*$. This is where I'm stuck at rn. Can someone help me finishing?

$\endgroup$
3
  • $\begingroup$ The extended Euclidean algorithm provides you a solution to $g = ax \pmod{n}$. Can you calculate one possible solution for $b$ from the above? What about all of the solutions? $\endgroup$
    – Haran
    Commented Jun 11, 2022 at 13:12
  • $\begingroup$ See the lnked dupe for how to solve a linear congruence, and see the worked examples there (and in the many linked questions there). $\endgroup$ Commented Jun 11, 2022 at 13:13
  • $\begingroup$ In part (a), $a$ does not need to be a unit. In $\mathbb{Z}_8$, there are solutions for $a=2, c=4$. I think part (b) is related to the fact this example has two solutions $b=2, b=6$. $\endgroup$
    – aschepler
    Commented Jun 11, 2022 at 13:13

0