1
$\begingroup$

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.

  • 2
    Can you please reformulate your question. Your title is not clear at all and as it stand true for any a, b.2012-02-28
  • 0
    @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.2012-02-28
  • 0
    Is it unclear ?2012-02-28
  • 0
    @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 given2012-02-28
  • 0
    @AndréNicolas : But $(5,6)$ is not "other". take $k=7$ then $(kA,kB) = (5,6)$.2012-02-28
  • 0
    @a-z: OK, so you are automatically reducing modulo $n$, which is the reasonable thing to do.2012-02-28

1 Answers 1

1

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,+)$

  • 0
    (At line 2) Do you mean $\rm\:(A,B,n) = 1,\:$ results $\rm\:(A,B)\equiv 1 (mod\ n)$ ?2012-02-28
  • 0
    @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$2012-02-28
  • 0
    if $A=B=5$ and $n=7$ then $\rm\:(A,B,n) = 1,\:$ but $\rm\:(A,B)\ = 5 \equiv 5$ not $1$2012-02-28
  • 0
    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.2012-02-28
  • 0
    Sorry but what does $\:xz,\:yz\equiv 0$ mean? If it means $\:xz \equiv 0$ and $\:yz\equiv 0$ then I don't know why $\rm\:ax+by\equiv 0\ \:\Rightarrow\ xz,\:yz\equiv 0$. And finally Why does $aB\equiv bA$ results $a\equiv kA$ and $b \equiv kB$ for some $k \in \mathbb Z$?2012-02-28
  • 0
    @a-z Yes, $\rm\:j,k \equiv 0\:$ means $\rm\:j\equiv0,\:k\equiv 0.$ If $\rm\:ax+by\equiv 0\:$ then, since $\rm\:Ax+By\equiv 0\:$ by hypothesis, the displayed equations reduce to $\rm\:(aB-bA)x\equiv 0,\ (aB-bA)y\equiv 0,\:$ i.e. $\rm\:zx,zy\equiv 0.$ Finally the theorem infers that $\rm\:aB\equiv bA\:$ not $\rm\:(a,b)\equiv k(A,B).$ The latter implies the former. Is the converse true?2012-02-28
  • 0
    I asked to prove $ax+by \equiv 0 \iff (a,b) \equiv k(A,B)$. And your theorem says $ax+by \equiv 0 \iff aB \equiv bA$. So the converse should be true.2012-02-28
  • 1
    @a-z I left the rest for you. Is it true or is there a counterexample? Look closely at the proof.2012-02-28
  • 0
    Thank you, I will think on the proof. But I didn't totally understand the last line and $(A,B,n)=1 \iff (A,B) \equiv 1$. Do I need knowledge about them for the rest of proof?2012-02-28
  • 0
    No, you don't need to understand ideals. You need only understand what I said in the Note, i.e. interpret $\rm\:(x,y)\equiv 1\:$ to mean that some linear combination $\rm\:(x,y)\:$ of $\rm\:x,y\:$ is $\equiv 1$. Please don't hesitate to ask if you have further questions. I didn't know if you knew about ideals. It helps to say something about your knowledge level either in your profile or in the question, so answerers can reply at the appropriate level.2012-02-28
  • 0
    I've thought but nothing connected to $(a,b) \equiv k(A,B)$. Please give more hints on last steps.2012-02-29