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.
$\begingroup$
$\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$– SudarsanNov 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$– AdamNov 19, 2013 at 20:39
-
1$\begingroup$ I love this question for its multiples answers, each answer is neat. $\endgroup$– SomeOneNov 22, 2013 at 21:04
-
$\begingroup$ ${\rm mod}\ 11\!:\ x\equiv 56x\equiv 65y\equiv -y\,\Rightarrow\, x+y\equiv 0\ \ $ $\endgroup$– Bill DubuqueApr 10, 2015 at 0:21
Add a comment
|
10 Answers
$\begingroup$
$\endgroup$
4
Why not just $x+y=(56x-55x)+(66y-65y)=11(6y-5x)+(56x-65y)=11(6y-5x)$ (since $56x-65y=0$).
-
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$– TonyKNov 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$– DocNov 18, 2013 at 22:01
-
$\begingroup$ @Kaz, you can always award a volunteer bounty :-) $\endgroup$– alexisNov 19, 2013 at 15:41
$\begingroup$
$\endgroup$
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.
answered Nov 18, 2013 at 1:01
$\begingroup$
$\endgroup$
1
$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$.
answered Nov 18, 2013 at 1:02
$\begingroup$
$\endgroup$
1
$56x = 65y \implies x + y = 11(6y - 5x)$
$\begingroup$
$\endgroup$
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$.
answered Nov 18, 2013 at 1:35
$\begingroup$
$\endgroup$
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)$.
$\begingroup$
$\endgroup$
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$.
answered Nov 18, 2013 at 2:44
$\begingroup$
$\endgroup$
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$....
$\begingroup$
$\endgroup$
$$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$
$\begingroup$
$\endgroup$
2
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.
-
1$\begingroup$ ?? Is 121/56 divisible by 11?? $\endgroup$– user99914Nov 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