Show that 5n + 3 and 7n + 4 are relatively prime for any n 2 N. Show that s and t are not unique.

Question

I know that s = 7 and t = -5, but I'm having trouble showing that they are not unique. I've been just guess and checking, is there a better way to compute this?

Answer 1

Note that$$7(5n+3)-5(7n+4)=1$$and therefore $5n+3$ and $7n+4$ are relatively prime. But it is also true that$$\bigl(7+(7n+4)\bigr)(5n+3)-\bigl(5+(5n+3)\bigr)(7n+4)=1.$$

Answer 2

Note that since

$$\gcd(a,b)=\gcd(a,b-a))$$

we have

$$\gcd(5n+3,7n+4)=\gcd(5n+3,2n+1)=\gcd(n+1,2n+1)=\gcd(n+1,n)=\gcd(n,1)=1$$

Thus for Bézout's theorem exist $s,t\in\mathbb{Z}$, not unique, such that

$$s\cdot(5n+3)+t\cdot(7n+4)=1$$

Answer 3

Note:

If $s(5n + 3) + t(7n + 4) = 1$

Then $s(5n+3) + K + t(7n + 4) - K = 1$

$(s + \frac K{5n+3})(5n+3) + (t - \frac K{7n+4})(7n+4) = 1$ .

So if $s, t$ are such that $s(5n + 3) + t(7n + 4) = 1$

Then $s + \frac K{5n+3}, $ and $t - \frac K{5n+3}$ are too.

Is it possible that there is an integer $K$ (other than $K = 0$) so that $\frac K{5n+3}$ and $\frac K{7n + 4}$ are both integers?

Is it possible that there could be more than one?

$K$ must be a multiple of $5n+3$ and $K$ must be a multiple $7n+4$. Is that possible? Is in possible that two different numbers could have a common multiple?

Answer 4

Since $$7(5n+3)-5(7n+4)=1 \text { (*) } $$ $5n+3$ and $7n+4$ are relatively prime.

In order to get other coefficients you may replace $5$ with $5$ times $\text { ( *)}$ or $7$ by $7$ times $\text { (*)}.$