Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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

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

share|improve this answer
    
(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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.