Sum of two co-prime integers
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.
number-theory elementary-number-theory
New contributor
|
show 1 more comment
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.
number-theory elementary-number-theory
New contributor
4
What's wrong with $n=1+(n-1)$? Perhaps you meant to require $a,b>1$ but you should specify that.
– lulu
Dec 15 at 16:03
1
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$.
– Mindlack
Dec 15 at 16:05
1
True i should have specified that a,b>1, sorry, my bad.
– Daniel Gimpelman
Dec 15 at 16:07
Daniel, you can edit your post. Also, have a look at this introduction to posting mathematical notation.
– hardmath
Dec 15 at 16:12
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.
– Daniel Gimpelman
Dec 15 at 16:25
|
show 1 more comment
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.
number-theory elementary-number-theory
New contributor
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.
number-theory elementary-number-theory
number-theory elementary-number-theory
New contributor
New contributor
edited Dec 15 at 17:17
Avi Steiner
2,693927
2,693927
New contributor
asked Dec 15 at 16:01
Daniel Gimpelman
184
184
New contributor
New contributor
4
What's wrong with $n=1+(n-1)$? Perhaps you meant to require $a,b>1$ but you should specify that.
– lulu
Dec 15 at 16:03
1
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$.
– Mindlack
Dec 15 at 16:05
1
True i should have specified that a,b>1, sorry, my bad.
– Daniel Gimpelman
Dec 15 at 16:07
Daniel, you can edit your post. Also, have a look at this introduction to posting mathematical notation.
– hardmath
Dec 15 at 16:12
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.
– Daniel Gimpelman
Dec 15 at 16:25
|
show 1 more comment
4
What's wrong with $n=1+(n-1)$? Perhaps you meant to require $a,b>1$ but you should specify that.
– lulu
Dec 15 at 16:03
1
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$.
– Mindlack
Dec 15 at 16:05
1
True i should have specified that a,b>1, sorry, my bad.
– Daniel Gimpelman
Dec 15 at 16:07
Daniel, you can edit your post. Also, have a look at this introduction to posting mathematical notation.
– hardmath
Dec 15 at 16:12
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.
– Daniel Gimpelman
Dec 15 at 16:25
4
4
What's wrong with $n=1+(n-1)$? Perhaps you meant to require $a,b>1$ but you should specify that.
– lulu
Dec 15 at 16:03
What's wrong with $n=1+(n-1)$? Perhaps you meant to require $a,b>1$ but you should specify that.
– lulu
Dec 15 at 16:03
1
1
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$.
– Mindlack
Dec 15 at 16:05
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$.
– Mindlack
Dec 15 at 16:05
1
1
True i should have specified that a,b>1, sorry, my bad.
– Daniel Gimpelman
Dec 15 at 16:07
True i should have specified that a,b>1, sorry, my bad.
– Daniel Gimpelman
Dec 15 at 16:07
Daniel, you can edit your post. Also, have a look at this introduction to posting mathematical notation.
– hardmath
Dec 15 at 16:12
Daniel, you can edit your post. Also, have a look at this introduction to posting mathematical notation.
– hardmath
Dec 15 at 16:12
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.
– Daniel Gimpelman
Dec 15 at 16:25
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.
– Daniel Gimpelman
Dec 15 at 16:25
|
show 1 more comment
4 Answers
4
active
oldest
votes
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 $kpm 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 $kpm 2$ is odd you have $gcd(k-2,k+2)=gcd(k-1, 4) = 1$.
add a comment |
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 $kgeq 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.
New contributor
2
+1 A nice combination of hint and solution.
– Ethan Bolker
Dec 15 at 16:25
add a comment |
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.$
add a comment |
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
$gcd(a, n - a) = 1$,
$1 < a < n$, and
$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. :-)
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Daniel Gimpelman is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3041656%2fsum-of-two-co-prime-integers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
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 $kpm 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 $kpm 2$ is odd you have $gcd(k-2,k+2)=gcd(k-1, 4) = 1$.
add a comment |
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 $kpm 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 $kpm 2$ is odd you have $gcd(k-2,k+2)=gcd(k-1, 4) = 1$.
add a comment |
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 $kpm 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 $kpm 2$ is odd you have $gcd(k-2,k+2)=gcd(k-1, 4) = 1$.
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 $kpm 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 $kpm 2$ is odd you have $gcd(k-2,k+2)=gcd(k-1, 4) = 1$.
answered Dec 15 at 21:35
fleablood
68.1k22684
68.1k22684
add a comment |
add a comment |
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 $kgeq 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.
New contributor
2
+1 A nice combination of hint and solution.
– Ethan Bolker
Dec 15 at 16:25
add a comment |
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 $kgeq 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.
New contributor
2
+1 A nice combination of hint and solution.
– Ethan Bolker
Dec 15 at 16:25
add a comment |
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 $kgeq 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.
New contributor
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 $kgeq 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.
New contributor
New contributor
answered Dec 15 at 16:23
RandomMathDude
1863
1863
New contributor
New contributor
2
+1 A nice combination of hint and solution.
– Ethan Bolker
Dec 15 at 16:25
add a comment |
2
+1 A nice combination of hint and solution.
– Ethan Bolker
Dec 15 at 16:25
2
2
+1 A nice combination of hint and solution.
– Ethan Bolker
Dec 15 at 16:25
+1 A nice combination of hint and solution.
– Ethan Bolker
Dec 15 at 16:25
add a comment |
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.$
add a comment |
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.$
add a comment |
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.$
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.$
edited Dec 15 at 21:21
answered Dec 15 at 18:33
Will Jagy
101k598198
101k598198
add a comment |
add a comment |
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
$gcd(a, n - a) = 1$,
$1 < a < n$, and
$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. :-)
add a comment |
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
$gcd(a, n - a) = 1$,
$1 < a < n$, and
$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. :-)
add a comment |
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
$gcd(a, n - a) = 1$,
$1 < a < n$, and
$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. :-)
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
$gcd(a, n - a) = 1$,
$1 < a < n$, and
$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. :-)
answered Dec 15 at 22:46
templatetypedef
4,54122357
4,54122357
add a comment |
add a comment |
Daniel Gimpelman is a new contributor. Be nice, and check out our Code of Conduct.
Daniel Gimpelman is a new contributor. Be nice, and check out our Code of Conduct.
Daniel Gimpelman is a new contributor. Be nice, and check out our Code of Conduct.
Daniel Gimpelman is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3041656%2fsum-of-two-co-prime-integers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
4
What's wrong with $n=1+(n-1)$? Perhaps you meant to require $a,b>1$ but you should specify that.
– lulu
Dec 15 at 16:03
1
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$.
– Mindlack
Dec 15 at 16:05
1
True i should have specified that a,b>1, sorry, my bad.
– Daniel Gimpelman
Dec 15 at 16:07
Daniel, you can edit your post. Also, have a look at this introduction to posting mathematical notation.
– hardmath
Dec 15 at 16:12
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.
– Daniel Gimpelman
Dec 15 at 16:25