2
$\begingroup$

This is the question and solution:

Q: Prove that for any integer $a$, $2a + 1$ and $4a^2$ + 1 are relatively prime. A: Since $4a^2 + 1 = (2a − 1)(2a + 1) + 2$, any common divisor of $2a + 1$ and $4a^2 + 1$ must be a divisor of $2$. This means that $d=1$ or $d=2$. However, $2$ is not a common divisor as both $2a + 1$ and $4a^2 + 1$ are odd. Therefore, the greatest common divisor must be $1$.

Can someone explain how they knew that the common divisor of $2a + 1$ and $4a^2 + 1$ would be a divisor of $2$ (the bolded portion)? Is this some number theory that I just don't know? Also, this topic is $\gcd$ (greatest common divisor in discrete mathematics). Thanks in advance.

$\endgroup$
0
$\begingroup$

I'll start with some examples with actual numbers...

Is $10$ a divisor of $20\times23=460$? Yes. Note that $10\mid20$. This gives us a general rule: If $d\mid a$, then $d\mid ab$.

Is $10$ a divisor of $580-110=470$? Yes. Note that $10\mid570$ and $10\mid110$. This gives us a general rule: If $d\mid a$ and $d\mid b$, then $d\mid a-b$.

(P.S. Those are not proofs, but I hope they give you an idea for why these things are true.)


So, we're assuming that this number, $d$, is a common divisor of $2a+1$ and $4a^2+1$.

Note that $d$ is a divisor of $(2a+1)(2a-1)$, because it's a divisor of one of the factors (our first rule).

We have: $$4a^2+1=(2a+1)(2a-1)+2$$ Subtracting $(2a+1)(2a-1)$ from both sides: $$(4a^2+1)-(2a+1)(2a-1)=2$$ From our second rule, $d$ divides this also.

$\endgroup$
  • $\begingroup$ By the way, our second rule can be amended slightly: If $d\mid a$ and $d\mid b$, then $d\mid a\pm b$. In other words, $d\mid a+b$ and $d\mid a-b$. $\endgroup$ – Akiva Weinberger Dec 7 '14 at 1:06
  • $\begingroup$ Ah, thanks so much! That was very helpful! $\endgroup$ – J.K Dec 7 '14 at 6:07
2
$\begingroup$

Suppose that $d\mid n$ and $d\mid kn+b$; then there are integers $\ell$ and $m$ such that $n=d\ell$ and $kn+b=dm$. Substitute the first equation into the second to find that $k(d\ell)+b=dm$ and hence that $b=dm-dk\ell=d(m-k\ell)$, so that $d\mid b$. Now apply this with $n=2a+1$, $k=2a-1$, and $b=2$.

More generally, you can prove similarly that if $d$ divides any two of $a,b$, and $a+b$, it divides the third.

$\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.