23
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Sudarsan Nov 18 '13 at 0:58
  • 3
    $\begingroup$ 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$. $\endgroup$ – Pedro Tamaroff Nov 18 '13 at 1:05
  • $\begingroup$ @Sudarsan: Could you expand upon your idea? Trying to follow it, I dont seem to be able to get anywhere. $\endgroup$ – Adam Nov 19 '13 at 20:39
  • 1
    $\begingroup$ I love this question for its multiples answers, each answer is neat. $\endgroup$ – SomeOne Nov 22 '13 at 21:04
  • $\begingroup$ ${\rm mod}\ 11\!:\ x\equiv 56x\equiv 65y\equiv -y\,\Rightarrow\, x+y\equiv 0\ \ $ $\endgroup$ – Bill Dubuque Apr 10 '15 at 0:21

10 Answers 10

63
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ A worthy contribution indeed, but how can it be worth 40 upvotes? I think even Doc must be wondering the same thing! $\endgroup$ – TonyK Nov 18 '13 at 18:43
  • 2
    $\begingroup$ @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. $\endgroup$ – BlueRaja - Danny Pflughoeft Nov 18 '13 at 21:51
  • 1
    $\begingroup$ @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. $\endgroup$ – Doc Nov 18 '13 at 22:01
  • $\begingroup$ @Kaz, you can always award a volunteer bounty :-) $\endgroup$ – alexis Nov 19 '13 at 15:41
31
$\begingroup$

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.

$\endgroup$
23
$\begingroup$

$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$.

$\endgroup$
  • $\begingroup$ nice solution dude. $\endgroup$ – HowardRoark Nov 20 '13 at 6:49
13
$\begingroup$

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

$\endgroup$
  • $\begingroup$ ⁺¹ for brevity. $\endgroup$ – Alfe Nov 18 '13 at 20:03
4
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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)$.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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$....

$\endgroup$
0
$\begingroup$

$$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$

$\endgroup$
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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