# What are all pairs $(a,b)$ such that if $Ax+By \equiv 0 \pmod n$ then we can conclude $ax+by = 0 \pmod n$?

All these are good pairs:

$$(0, 0), (A, B), (2A, 2B), (3A, 3B), \ldots \pmod{n}$$

But are there any other pairs?

actually it was a programming problem with $A,B,n \leq 10000$ but it seems to have a pure solution.

-
Can you please reformulate your question. Your title is not clear at all and as it stand true for any a, b. – Nicky Hekster Feb 28 '12 at 9:29
@NickyHekster That was partially my fault, I changed some capitalizations because a couple were clearly wrong, but changed to many. However the question still makes no sense. – Alex Becker Feb 28 '12 at 9:44
Is it unclear ? – a-z Feb 28 '12 at 9:47
@a-z unclear is one thing,if there is given (A,B) and you are looking for (a,b) then it seems that they are different and maybe (a,b) are some combination of (A,B) or others,so guys are asking to define exactly why do you need (a,b) when (A,B) are given – dato datuashvili Feb 28 '12 at 10:34
@AndréNicolas : But $(5,6)$ is not "other". take $k=7$ then $(kA,kB) = (5,6)$. – a-z Feb 28 '12 at 13:40

If $\rm\:c\ |\ A,B,n\:$ cancel $\rm\:c\:$ from $\rm\:Ax + By = nk.\:$ So w.l.o.g. $\rm\:(A,B,n) = 1,\:$ i.e. $\rm\:(A,B)\equiv 1$.
Similarly, restricting to "regular" $\rm\:x,y,\:$ those such that $\rm\:(x,y,n) = 1,\:$ i.e. $\rm\:(x,y)\equiv 1,\:$ yields

Theorem $\rm\:\ If\:\ (A,B)\equiv 1\equiv (x,y)\:\ and\:\ Ax+By\equiv 0,\ then\:\ ax+by\equiv 0\iff aB\equiv bA$

Proof $\$ One easily verifies $$\rm\:\ \ B(ax+by)\: =\: (aB-bA)x + b(Ax+By)$$ $$\rm -A(ax+by)\: =\: (aB-bA)y - a(Ax+By)$$

$(\Rightarrow)\$ Let $\rm\:z = aB-bA.\:$ By above $\rm\:ax+by\equiv 0\ \:\Rightarrow\ xz,\:yz\equiv 0 \ \Rightarrow\ z \equiv (x,y)z\equiv 0$.

$(\Leftarrow)\$ Let $\rm\:z = ax+by.\:$ By above $\rm\:aB-bA\equiv 0\ \Rightarrow\ Az,Bz\equiv 0\ \Rightarrow\ z \equiv (A,B)z\equiv 0.\ \$ QED

Note $\rm\ (x,y)\equiv 1\pmod n\:$ means $\rm\:ix+jy = 1 + kn\:$ for some $\rm\:i,j,k\in \mathbb Z$

Thus we infer $\rm\:xz,yz\equiv 0\ \Rightarrow z \equiv (ix+jy)z\equiv i(xz)+j(yz)\equiv 0\pmod n$

i.e. $\rm\ \ ord(z)\ |\ x,y\ \Rightarrow\ ord(z)\ |\ (x,y) = 1\$ in the additive group $\rm\:(\mathbb Z/n,+)$

-
(At line 2) Do you mean $\rm\:(A,B,n) = 1,\:$ results $\rm\:(A,B)\equiv 1 (mod\ n)$ ? – a-z Feb 28 '12 at 18:43
@a-z See the Note. Both are equivalent to $\rm\:i A + j B + k n = 1\:$ for some $\rm\:i,j,k\in \mathbb Z$ – Bill Dubuque Feb 28 '12 at 18:51
if $A=B=5$ and $n=7$ then $\rm\:(A,B,n) = 1,\:$ but $\rm\:(A,B)\ = 5 \equiv 5$ not $1$ – a-z Feb 28 '12 at 19:19
In $\rm\:\mathbb Z/ 7\:$ holds $(5,5) = (5) = (1)\:$ since $5$ is a unit. As I said $\rm\: I = (x,y,z) = 1\:$ means $\rm\:I = (1)\:$ i.e. $\rm\:i x + j y + k z = 1\:$ for some $\rm\:i,j,k\:$ in the ambient ring, i.e. it's an ideal equality, which happens to be equivalent to saying that $\rm\:gcd(x,y,z) = 1\:$ in rings like $\rm\:\mathbb Z\:$ whose gcds are linearly representable (Bezout identity). In general rings, gcds are defined only up to unit factors. – Bill Dubuque Feb 28 '12 at 19:45
@a-z I left the rest for you. Is it true or is there a counterexample? Look closely at the proof. – Bill Dubuque Feb 28 '12 at 21:43