# Prove if $56x = 65y$ then $x + y$ is divisible by $11$

If $x$ and $y$ are natural numbers, and $56x = 65y$, prove that $x + y$ is divisible by $11$.

I tried taking the $\gcd(56x,65y)$ using the Euclidean algorithm, but I got nowhere with it and do not know where to head.

• Why go that far? Substitute either for $x$ or for $y$ from $56x=65y$ in $x+y$ and see that the result is always divisible by 11. – Sudarsan Nov 18 '13 at 0:58
• As noted by Andre, what you want to observe is that $\mod 11$, $56=1$ and $65=-1$. This means $x+y=0\mod 11$. – Pedro Tamaroff Nov 18 '13 at 1:05
• @Sudarsan: Could you expand upon your idea? Trying to follow it, I dont seem to be able to get anywhere. – Adam Nov 19 '13 at 20:39
• I love this question for its multiples answers, each answer is neat. – SomeOne Nov 22 '13 at 21:04
• ${\rm mod}\ 11\!:\ x\equiv 56x\equiv 65y\equiv -y\,\Rightarrow\, x+y\equiv 0\ \$ – Bill Dubuque Apr 10 '15 at 0:21

## 10 Answers

Why not just $x+y=(56x-55x)+(66y-65y)=11(6y-5x)+(56x-65y)=11(6y-5x)$ (since $56x-65y=0$).

• A worthy contribution indeed, but how can it be worth 40 upvotes? I think even Doc must be wondering the same thing! – TonyK Nov 18 '13 at 18:43
• @Tony: The more people that can understand an answer, the more upvotes it gets. This leads to the most trivial questions/answers getting the most upvotes. This is an issue across all the SE sites, not just this one. – BlueRaja - Danny Pflughoeft Nov 18 '13 at 21:51
• @Tony, you are 100% correct. But (also addressed @BlueRaja), I prefer to think that even those who are capable of understanding any and all solutions still appreciate a solution that appeals to those with a more limited background. – Doc Nov 18 '13 at 22:01
• @Kaz, you can always award a volunteer bounty :-) – alexis Nov 19 '13 at 15:41

We have $56x\equiv x\pmod{11}$ and $65y\equiv -y \pmod{11}$. If $56x=65y$, it follows that $x\equiv -y\pmod{11}$, which is what we needed to show.

$56$ and $65$ are relatively prime, so if $56x=65y$, then $65\mid x$ and $56\mid y$; say $x=65m$ and $y=56n$. Then

$$56\cdot65m=56x=65y=65\cdot56n\;,$$

so $m=n$. Thus, the solutions are of the form $x=65k,y=56k$ for integers $k$, and $$x+y=(65+56)k=121k=11(11k)\;.$$

Thus, $x+y$ is even divisible by $11^2$.

• nice solution dude. – HowardRoark Nov 20 '13 at 6:49

$56x = 65y \implies x + y = 11(6y - 5x)$

• ⁺¹ for brevity. – Alfe Nov 18 '13 at 20:03

Since $11$ does not divide $56$ and $11$ is prime, $11$ divides $x+y$ if and only if it divides $56(x+y)$. But $56(x+y)=56x+56y=65y+56y=121y$, which in fact is divisible by $11^2$.

Another variation (short, strong result, explicitly invoking Gauss lemma) :

Adding $56y$ to both members gives $56(x+y) = 121y$. Since $56$ and $121$ are relatively prime, by Gauss, $121$ divides $(x+y)$.

Let's work in $\mathbb R^2$. We have a linear map given by the matrix $$A=\begin{pmatrix}65 & -56\\1&1\end{pmatrix}$$ And we are interested in the solutions to the equation $A\mathbf x=\begin{pmatrix}0\\ b\end{pmatrix}$ where $b$ is an integer. Since the determinant of $A$ is $121$, Cramer's rule implies that the first coordinate of the solution $\mathbf x$ is $\frac {56b}{121}$. Thus, if $\mathbf x$ has integer coordinates, then $b$ is a multiple of $121$.

From here the idea is pretty straight forward to generalize. If $r,s$ are integers such that $d=65r+56s$ is relatively prime to both $56$ and $65$, then any pair of integers $x,y$ for which $65x=56y$ satisfies $rx+sy\equiv 0\pmod d$.

This is basically the same as the answer by Brian M. Scott:

$$65(x+y)=65x+65y=65x+56x=121x$$

Thus $11^2 | 65(x+y)$ and since it is relatively prime to $65$....

$$56x=65y\tag1$$ $$x+y=\frac{56}{56}(x+y)=\frac{56x+56y}{56}$$ from (1) we have $$\frac{65y+56y}{56}=\frac{121y}{56}=\frac{11^2y}{56}\tag2$$ As $121$ is not divisible by 56, so $56|y$ or $y = 56 n$ which helps us to deduce $$x+y = 11^2n$$ or $11|x+y$

56x = 65y

x = (65/56) y

x + y = (65/56)y + (56/56)y = (121/56)y

It is obvious that (121/56) is divisible by 11.

• ?? Is 121/56 divisible by 11?? – user99914 Nov 19 '13 at 20:50
• Technically, he has shown that $56(x+y)$ is divisible by $11$ and therefore that $x+y$ is divisible by $11$. – Thomas Andrews Nov 19 '13 at 21:08