Let $a$ be a positive integer such that $\gcd(an+1, 2n+1) = 1$ for all integer $n$. a) Prove that $\gcd(a-2, 2n+1) = 1$ for all integer $n$. b) Find all possible $a$.
Problem
Source: Indonesian National Science Olympiad 2018, Mathematics P1
Tags: number theory, relatively prime
06.07.2018 09:09
Suppose $p|a-2\wedge p|2n+1$ and $p$ is prime. Then $p|an-2n=an+1-(2n+1)\implies p|an+1$. Because $\gcd(an+1, 2n+1) = 1$, there doesn't exist such prime $p$ that $p|2n+1\wedge p|an+1$. Contradiction proves a).
06.07.2018 10:53
(a) using the euclidean algorithm an+1=(2n+1)+(a-2)n so (an+1,2n+1)=(2n+1,(a-2)n)=1 so (2n+1,a-2)=1 (b) a is of the form 2^x+2 or a=1,3 pf) if a is an even number let a=2k an+1=(2n+1)k-k+1 K-1 has to be of the form 2 to the power of something so a=2^x+2 if a is odd a=1 and a=3 if a is greater than 3 let a=2k+1 where k is greater than 1 then if n=3k-2, (an+1,2n+1)=2k-1 this doesn't work Is this correct?
22.08.2018 23:09
chaotic_iak wrote: Let $a$ be a positive integer such that $\gcd(an+1, 2n+1) = 1$ for all integer $n$. a) Prove that $\gcd(a-2, 2n+1) = 1$ for all integer $n$. b) Find all possible $a$. Solution. a). Recalling $\gcd(xy,z)=1\iff\gcd(x,z)=\gcd(y,z)=1$, using the euclidean algorithm we obtain \begin{align*}\gcd(an+1, 2n+1) = 1\Longrightarrow&\gcd(an+1-(2n+1), 2n+1) = 1\\ \Longrightarrow&\gcd((a-2)n, 2n+1) = 1\\ \Longrightarrow&\gcd(a-2, 2n+1) = 1. \end{align*}b). Since that $\gcd(a-2, 2n+1) = 1$ holds for all integer $n$, we obtain $\gcd(a-2, p) = 1$ for all prime $p>2$ by putting $n=\frac{p-1}{2}$, which implies that $a-2=\pm2^m$ for some integer $m\ge0$. Clearly $\gcd\left(\pm2^m,2n+1\right)=1$ for all nonnegative integer $m$ and all integer $n$. Therefore, all possible $a$ are $1$ or $2+2^m$ for any nonnegative integer $m$. $\blacksquare$
07.09.2022 02:59
no that is not true because gcd( 2n+1 , n ) = 1 so a can be 3
03.10.2022 03:15
mmrazavi wrote: no that is not true because gcd( 2n+1 , n ) = 1 so a can be 3 $m$ is non-negative integer, so $3$ is already mentioned by using $m=0$