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$
5
  • $\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, 2013 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
    Nov 18, 2013 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, 2013 at 20:39
  • 1
    $\begingroup$ I love this question for its multiples answers, each answer is neat. $\endgroup$
    – SomeOne
    Nov 22, 2013 at 21:04
  • $\begingroup$ ${\rm mod}\ 11\!:\ x\equiv 56x\equiv 65y\equiv -y\,\Rightarrow\, x+y\equiv 0\ \ $ $\endgroup$ Apr 10, 2015 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$
4
  • 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, 2013 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$ Nov 18, 2013 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, 2013 at 22:01
  • $\begingroup$ @Kaz, you can always award a volunteer bounty :-) $\endgroup$
    – alexis
    Nov 19, 2013 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$
1
  • $\begingroup$ nice solution dude. $\endgroup$ Nov 20, 2013 at 6:49
13
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ ⁺¹ for brevity. $\endgroup$
    – Alfe
    Nov 18, 2013 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$
2
  • 1
    $\begingroup$ ?? Is 121/56 divisible by 11?? $\endgroup$
    – user99914
    Nov 19, 2013 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$ Nov 19, 2013 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.