模n同余方程[b]⊙[x]=[c]有解时证明d|c的思路问询

Hey there, you're already on the right track with writing the gcd as a linear combination—let's connect that to the ring equation you have, step by step:

• First, translate the ring operation back to integer arithmetic:
  The equation [b]⊙[x] = [c] having a solution [a] in Zₙ means, in regular integers, that b*a ≡ c mod n. By definition of congruence, this means there exists some integer k such that:

  b*a - c = n*k
  

  Rearranged, this gives us:

  c = b*a - n*k
  

  This is the key link between the ring condition and integer linear combinations.

• Next, recall what d = gcd(b,n) implies:
  By definition of the greatest common divisor, d divides both b and n (written d | b and d | n). A fundamental property of gcds is that d divides every integer linear combination of b and n—any expression of the form b*m + n*l where m,l are integers is a multiple of d.

• Finally, put it all together:
  Look at the expression we got for c: it's exactly a linear combination of b and n (with coefficients a and -k). Since d divides all such combinations, it must divide c—that's exactly what you need to prove!

Your initial thought about writing d = b*p + n*q is perfect for reinforcing this: since d itself is a linear combination of b and n, every other linear combination (like c) has to be a multiple of d.

内容的提问来源于stack exchange，提问作者Charles Grealy