Prove that any integer greater than or equal to $7$ can be written as a sum of two relatively prime integers, both greater than $1$.For example, $22$ and $15$ are relatively prime, and thus $37 = 22+15$ represents the number $37$ in the desired way
$\begingroup$
$\endgroup$
7
-
$\begingroup$ Can you find a general way to do any odd number? (Those are the easiest.) $\endgroup$– ArthurJun 28, 2016 at 7:09
-
$\begingroup$ @ThomasAndrews yes n + n+1 $\endgroup$– user347954Jun 28, 2016 at 7:11
-
$\begingroup$ i tried for even numbers what i did is write them in form of 7+k where k is not a multiple of 7 $\endgroup$– user347954Jun 28, 2016 at 7:12
-
1$\begingroup$ @barakmanos how do we prove existence of such d in our set ? $\endgroup$– user347954Jun 28, 2016 at 7:23
-
2$\begingroup$ The easiest way is to show that $\phi(n)>2$, so there must be such a $d$. Note that $\phi(3)=\phi(4)=\phi(6)=2$, so it is not true for $n=3,4,6$. $\endgroup$– Thomas AndrewsJun 28, 2016 at 7:30
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
5
If $n=2k+1$ then $k,k+1$ are relatively prime.
If $n=4k$ then $2k-1,2k+1$ are relatively prime.
If $n=4k+2$ then $2k-1,2k+3$ are relatively prime.
answered Jun 28, 2016 at 7:37
-
1$\begingroup$ The last two cases can be combined into $4k+2=(2k-3)+(2k+5)$. $\endgroup$ Jun 28, 2016 at 9:13
-
$\begingroup$ @ThomasAndrews how do we find these pairs of relatively prime integers is there a particular method you used or you randomly picked them so that their sum is the required number and checked if they were relatively prime $\endgroup$ Jun 28, 2016 at 9:47
-
1$\begingroup$ Actually, $2k-1,2k+3$ also works. @GerryMyerson $\endgroup$ Jun 28, 2016 at 12:10
-
1$\begingroup$ @user347954 I did trial and error. After the odd case, I figured out the $4k$ case. Numbers which are close together are easier to prove to be relatively prime. As noted by a previous comment, it was actually easier to do the $4k+2$ cases all at once. $\endgroup$ Jun 28, 2016 at 12:14
-
$\begingroup$ Edited to make the $4k+2$ case easier. $\endgroup$ Jun 28, 2016 at 12:44