1
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Can you find a general way to do any odd number? (Those are the easiest.) $\endgroup$
    – Arthur
    Jun 28, 2016 at 7:09
  • $\begingroup$ @ThomasAndrews yes n + n+1 $\endgroup$
    – user347954
    Jun 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$
    – user347954
    Jun 28, 2016 at 7:12
  • 1
    $\begingroup$ @barakmanos how do we prove existence of such d in our set ? $\endgroup$
    – user347954
    Jun 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$ Jun 28, 2016 at 7:30

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
5
  • 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$
    – user347954
    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

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.