# Math Help - Relatively Prime

1. ## Relatively Prime

Show that $5n+3$ and $7n+4$ are relatively prime for all $n$.

So we can find integers $x$ and $y$ such that $(5n+3)x + (7n+4)y = 1$ for all $n$. But I don't think this would be a very efficient way of doing this because you have to check it for all $n$.

Maybe we could to the following: Show that $7n+4$ has a multiplicative inverse modulo $5n+3$? So show that there exists an integer $y$ such that $(7n+4)y \equiv 1 (\text{mod} \ (5n+3))$?

2. Originally Posted by Sampras
Show that $5n+3$ and $7n+4$ are relatively prime for all $n$.

So we can find integers $x$ and $y$ such that $(5n+3)x + (7n+4)y = 1$ for all $n$. But I don't think this would be a very efficient way of doing this because you have to check it for all $n$.

Maybe we could to the following: Show that $7n+4$ has a multiplicative inverse modulo $5n+3$? So show that there exists an integer $y$ such that $(7n+4)y \equiv 1 (\text{mod} \ (5n+3))$?
Have you come across the Euclidean algorithm?

By hand, it is possible, but generally quite tedious (methinks this example, however, is rigged to work...). You want to get rid of your $5n$ and $7n$ with your choices of $x$ and $y$, so can you perhaps think of a way of choosing them such that $5n*x+7n*y = 0$? Then plugging in these $x$ and $y$ we, mircaulously, get our answer!...

3. $x = 5$, and $y = -5$.

4. Originally Posted by Sampras
$x = 5$, and $y = -5$.
Uh ?

$5(5)+7(-5)=-10\neq 0$

$5n*x+7n*y = 0$
Factor by n : n(5x+7y)=0
Now fix x, for example x=7... can you find a value for y such that it works ?

5. Originally Posted by Sampras
Show that $5n+3$ and $7n+4$ are relatively prime for all $n$.

So we can find integers $x$ and $y$ such that $(5n+3)x + (7n+4)y = 1$ for all $n$. But I don't think this would be a very efficient way of doing this because you have to check it for all $n$.

Maybe we could to the following: Show that $7n+4$ has a multiplicative inverse modulo $5n+3$? So show that there exists an integer $y$ such that $(7n+4)y \equiv 1 (\text{mod} \ (5n+3))$?
Let $d$ be a divisor then $5n\equiv -3(\bmod d)$ and $7n\equiv -4(\bmod d)$. Therefore, $35n\equiv -21(\bmod d)$ and $35n\equiv -20(\bmod d)$ so $-21\equiv -20(\bmod d)$ which means $d|1$.
Thus, $(5n+3,7n+4)=1$ for all $n$.

6. Originally Posted by Moo
Uh ?

$5(5)+7(-5)=-10\neq 0$

Factor by n : n(5x+7y)=0
Now fix x, for example x=7... can you find a value for y such that it works ?
$n(5x+7y) = 0$. Fix $x = 7$. Then $n(35+7y) = 0$. So $y = -35/7 = - 5$. Or in general, $y = 5x_{0}/7$.

7. Originally Posted by Sampras
$x = \color{red}7\color{black}$, and $y = -5$.
Fixed your typo. That should work now.

$(5n+3)(7)+(7n+4)(-5)\ =\ 1$