Library / Berkeley Math Circle: Monthly Contest 5 /3 of 16

Berkeley Math Circle: Monthly Contest 5

Number theory Difficulty 4.7 AIME Prove it United States

Problem:
Let $n$ be a positive integer. Show that $2n+1$ and $4n^{2}+1$ are relatively prime, that is, their only common factor is $1$ .

Solution

Solution:
Any common factor of the two numbers would also have to divide
$(4n^{2}+1)-(2n+1)(2n-1) = (4n^{2}+1)-(4n^{2}-1) = 2$
But both numbers are odd, since they are $1$ more than an even number, so they are not divisible by $2$ . Thus, their greatest common factor is $1$ .

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.