1. ## Relatively Prime

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

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

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

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

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

Maybe we could to the following: Show that $\displaystyle 7n+4$ has a multiplicative inverse modulo $\displaystyle 5n+3$? So show that there exists an integer $\displaystyle y$ such that $\displaystyle (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 $\displaystyle 5n$ and $\displaystyle 7n$ with your choices of $\displaystyle x$ and $\displaystyle y$, so can you perhaps think of a way of choosing them such that $\displaystyle 5n*x+7n*y = 0$? Then plugging in these $\displaystyle x$ and $\displaystyle y$ we, mircaulously, get our answer!...

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

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

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

$\displaystyle 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 $\displaystyle 5n+3$ and $\displaystyle 7n+4$ are relatively prime for all $\displaystyle n$.

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

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

6. Originally Posted by Moo
Uh ?

$\displaystyle 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 ?
$\displaystyle n(5x+7y) = 0$. Fix $\displaystyle x = 7$. Then $\displaystyle n(35+7y) = 0$. So $\displaystyle y = -35/7 = - 5$. Or in general, $\displaystyle y = 5x_{0}/7$.

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

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