3
$\begingroup$

I need some help in a proof: Prove that for any integer $n>6$ can be written as a sum of two co-prime integers $a,b$ s.t. $\gcd(a,b)=1$.

I tried to go around with "Dirichlet's theorem on arithmetic progressions" but didn't had any luck to come to an actual proof. I mainly used arithmetic progression of $4$, $(4n,4n+1,4n+2,4n+3)$, but got not much, only to the extent of specific examples and even than sometimes $a,b$ weren't always co-prime (and $n$ was also playing a role so it wasn't $a+b$ it was $an+b$).

I would appriciate it a lot if someone could give a hand here.

$\endgroup$
  • 4
    $\begingroup$ What's wrong with $n=1+(n-1)$? Perhaps you meant to require $a,b>1$ but you should specify that. $\endgroup$ – lulu Dec 15 '18 at 16:03
  • 1
    $\begingroup$ Dirichlet’s theorem is useless in that kind of situation; the problem is much, much simpler. Aside from the obvious case $n=(n-1)+1$, you can try to find general patterns when $n=4m$, $n=2m+1$, $n=4m+2$. $\endgroup$ – Mindlack Dec 15 '18 at 16:05
  • 1
    $\begingroup$ True i should have specified that a,b>1, sorry, my bad. $\endgroup$ – Daniel Gimpelman Dec 15 '18 at 16:07
  • $\begingroup$ Daniel, you can edit your post. Also, have a look at this introduction to posting mathematical notation. $\endgroup$ – hardmath Dec 15 '18 at 16:12
  • $\begingroup$ Mindlack thanks, but I don't really understand how to go from here. How do I represent a and b even in a specific case? $7=2*3+1$ where $a=2$ and $b=1$? $8=4*2$ where $a=4$ and $b=0$? (And than b isn't co-prime). $10=4*2+2$ where $a=4$ and $b=2$ (a,b aren't co-prime). Also there would always be the m, which i'm not sure if the m could be greater than 1. $\endgroup$ – Daniel Gimpelman Dec 15 '18 at 16:25
2
$\begingroup$

Well if $n$ is odd you can always do $n-2$ and $2$. Or you can do $\frac {n-1}2$ and $\frac {n+1}2$.

If $n = 2k$ and $k$ is even you can do $k-1$ and $k+1$. As $k\pm 1$ is odd and $\gcd(k-1, k+1) = \gcd(k-1, k+1 -(k-1)) = \gcd(k-1,2)=1$.

If $n = 2k$ and $k$ is odd you can do $k-2$ and $k+2$ and as $k\pm 2$ is odd you have $\gcd(k-2,k+2)=\gcd(k-1, 4) = 1$.

$\endgroup$
6
$\begingroup$

Just to provide an answer synthesized out of the comments already posted, your best (read as easiest) approach to this kind of problem is to toy around with general patterns until something either clicks and you can write a clever proof or until you accidentally exhaust all possible cases.

In this particular problem, we can break down cases into the residue classes $\bmod 4$ in order to hunt for patterns:

1) If $n=2k+1$ then the decomposition $n=(k)+(k+1)$ satisfies our criterion since consecutive numbers are always coprime and $k\geq 3$.

2) If $n=4k$ then consider the decomposition $n=(2k-1)+(2k+1)$. Are these numbers coprime? We can no longer rely upon the general fact that consecutive numbers are coprime, since these are not consecutive. However, if two numbers differ by exactly $2$, what is the only prime factor that they can share? In general, if two numbers differ by $m$, what prime factors can they share? Finally, are we sure that these numbers are both greater than $1$?

I have basically given away the entire answer, but I didn't know how to discuss this phenomenon in any other way, so I leave the final details of the second case, and the entirety of the third case, to you.

$\endgroup$
  • 2
    $\begingroup$ +1 A nice combination of hint and solution. $\endgroup$ – Ethan Bolker Dec 15 '18 at 16:25
1
$\begingroup$

Later: the numbers between $1$ and $n-1$ that are relatively prime to $n$ itself come in pairs that add up to $n$ and are relatively prime to each other as well. If $n=5$ or $n \geq 7$ both such numbers can be chosen strictly larger than $1.$

Original:

A different emphasis: if Euler's totient $\phi(n) \geq 3,$ then there is some integer $a$ with $\gcd(a,n) = 1$ and $1 < a < n-1.$ If we then name $b = n-a,$ we find that $\gcd(a,b) = 1$ as well, since a prime $p$ that divides both $a,n-a$ also divides $n,$ and this contradicts $\gcd(a,n) = 1.$

So, when is $\phi(n) \geq 3 \; ? \; \;$ If $n$ is divisible by any prime $q \geq 5,$ then $\phi(n)$ is a multiple of $\phi(q) = q-1,$ and that is at least $4.$

Next, if $n = 2^c \; 3^d \; . \;$ When $d=0$ we find $\phi(n) = 2^{c-1}$ is at least $3$ when $c \geq 3,$ leaving $2,4$ out. When $c=0$ we find $\phi(n) = 2 \cdot 3^{d-1}$ is at least $3$ when $d \geq 2,$ leaving $3$ out. When $c,d \geq 1,$ we find $\phi(n) = 2^c \cdot 3^{d-1}$ is at least $3$ when either $c \geq 2$ or $d \geq 2,$ so this leaves out $6.$

Put it together, for $n=5$ or $n \geq 7,$ there is some $a$ with $1 < a < n-1$ and $\gcd(a,n) = 1.$

$\endgroup$
1
$\begingroup$

Here's another route you can take to solve this problem. For any $n \ge 7$, you want to show that there is a number $a$ where

  1. $gcd(a, n - a) = 1$,
  2. $1 < a < n$, and
  3. $1 < n - a < n$.

One option would be to choose $a$ to be the smallest prime number that doesn't divide $n$. In that case, $gcd(a, n - a) = 1$ because otherwise you'd have $gcd(a, n - a) = a$, meaning that $a$ divides $a + (n - a) = n$, contradicting the fact that $a$ doesn't divide $n$.

What you'll need to then show is that if you pick $n \ge 7$ that the smallest prime number that doesn't divide $n$ happens to be less than $n - 1$. I'll leave that as an exercise to the reader. :-)

$\endgroup$

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.