1
$\begingroup$

I am trying to show that $7n + 4$ and $5n + 3$ are coprime for all $n \in \mathbb Z$ but I'm stuck.

Please could someone tell me how to show this?

What I tried:

My first attempt was to use that two numbers are coprime iff their $\gcd$ is $1$. So assume that there are integers $k,q$ such that $1 = 7kn + 4k + 5qn + 3q$.

And this is where my first attempt ended as I did not see a way to proceed from there.

My second attempt was to use that if $b> a$ then $\gcd(a,b) = \gcd(b, b-a)$ so

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

but this idea also seems to lead nowhere as I don't see how to show that $\gcd (5n + 3, 2n + 1)=1$.

$\endgroup$
  • 6
    $\begingroup$ You only started. Repeat the dose! $$(5n+3)-(2n+1)=3n+2,\ldots$$ Soon this may turn into full blown Euclid's algorithm :-) $\endgroup$ – Jyrki Lahtonen Aug 23 '15 at 6:47
  • $\begingroup$ As Jyrki said. Also, \gcd gets the upright version. $\endgroup$ – user21820 Aug 23 '15 at 6:52
3
$\begingroup$

Using the fact that if $b>a$, then $\gcd(a,b) = \gcd(b, b-a)$, we have:

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

$\endgroup$
6
$\begingroup$

A quick way is to eliminate $n$, noting that $7(5n+3)-5(7n+4)=1$.

$\endgroup$
1
$\begingroup$

Let $d$ be the $\gcd$. Then, $d|(5n+3-2n-1)=(3n+2), d|(3n+2-2n-1)=(n+1),d|(2n+1-2(n+1))=-1$ and so $d=1$.

$\endgroup$
-1
$\begingroup$

You can find $a,b$ such that: $a(7n+4) + b(5n+3) = 1\to 7a+5b=0, 4a+3b=1\to -21a-15b=0, 20a+15b=5\to a = -5, b = 7$. This means $\gcd(7n+4,5n+3) = 1$.

$\endgroup$

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.