# Solving $c = ab$ in $(\mathbb{Z}_n,+)$ [duplicate]

I need some help solving b).

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?

• 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? Commented Jun 11, 2022 at 13:12
• See the lnked dupe for how to solve a linear congruence, and see the worked examples there (and in the many linked questions there). Commented Jun 11, 2022 at 13:13
• 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$. Commented Jun 11, 2022 at 13:13