What solutions does the equation $4x\equiv2\mod10$ have? (Hint, it will have more that one.) What about solutions to an equation $ax\equiv d\mod n$, where $d=\gcd(a,n)$?
This is the question that appeared in our universities last year paper. But it seems very difficult for me like for first part I am able to solve by simplifications I got $x=5\cdot Z +3$ as solution which makes sense and seems fair but for the second one, I have no idea how can I approach that. Can you please help me out with that one. I tried to simplify that by using Euclidean algorithm but still, I didn't get any idea that what actually the solution will be. My final exam is on 2nd of next month and because of covid I am unable to contact in person for any help. So any help from this site will be appreciated. Thank you for looking at this question!
Let $a = Ad$ , $n = Nd$
so $gcd(A,N) = 1$
$Adx = d + kNd$
$Ax = 1 \mod{N}$
$x = A^{-1} \mod{N}$ , has one solution $\mod{N}$ since $gcd(A,N) = 1$
$0 \leq x = A^{-1} + k_2N \lt n \mod{n}$ , $k_2 = 0..(d-1)$
So there are $d$ solutions $\mod{n}$.