Homework Question:
Let n ∈ Z_+ be fixed. Let b,c ∈ Z and let d = gcd(b,n). Suppose the equation [b]⊙[x] = [c] has a solution [a] in Z_n, ie [b]⊙[a] = [c], where [a] ∈ Z_n.
Show that d divides c.
I am stuck on how to approach this, can someone give me a hint? More specifically I don't know what to do with this piece of information: [b]x=[c].
Thanks in advance.
P.S. apologies on any bad formatting
My attempt:
Writing the gcd as a linear combination we have d = bp + nq, where p,q ∈ Z.
We can also write [b]⊙[x]=[c] as bx ≡ c (modn)
If x is a solution, then bx = c + ny where y ∈ Z. Then c = bx - ny
To show d divides c:
bx - ny = k(bp + nq) where k ∈ Z
Thus bx - ny = bkp + nkq
Hence bk and nk both divide c so the linear combination also divides c.
The equation you write $[b]\odot[x]=[c]$ can be translated into $$ bx\equiv c\pmod{n} $$ Suppose $x$ is a solution, so $bx=c+ny$ for some $y$. Then $$ c=bx-ny $$ Conclude.