0
$\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$
  • $\begingroup$ Can you find a general way to do any odd number? (Those are the easiest.) $\endgroup$ – Arthur Jun 28 '16 at 7:09
  • $\begingroup$ @ThomasAndrews yes n + n+1 $\endgroup$ – user347954 Jun 28 '16 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 '16 at 7:12
  • 1
    $\begingroup$ @barakmanos how do we prove existence of such d in our set ? $\endgroup$ – user347954 Jun 28 '16 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 Andrews Jun 28 '16 at 7:30
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$
  • 1
    $\begingroup$ The last two cases can be combined into $4k+2=(2k-3)+(2k+5)$. $\endgroup$ – Gerry Myerson Jun 28 '16 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 '16 at 9:47
  • 1
    $\begingroup$ Actually, $2k-1,2k+3$ also works. @GerryMyerson $\endgroup$ – Thomas Andrews Jun 28 '16 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$ – Thomas Andrews Jun 28 '16 at 12:14
  • $\begingroup$ Edited to make the $4k+2$ case easier. $\endgroup$ – Thomas Andrews Jun 28 '16 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.