Mixing
Number of pairs $(a,b)$ such that $a+b<n$ and such that $gcd(a,b,n)=1$
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Let $n$ be a positive integer.
What is the number of pairs $(a,b)$ of positive integers such that $a+b<n$ and such that $gcd(a,b,n)=1$?
I know that the number of positive integer $a$ such that $gcd(a,n)=1$ is just $varphi(n)$. Maybe we can express the answer for my question above in terms of $varphi(n)$ and other arithmetic functions.
elementary-number-theory arithmetic-functions
asked Jul 17 at 17:07
raja.damanik
518
add a comment |Â
up vote
2
down vote
favorite
Let $n$ be a positive integer.
What is the number of pairs $(a,b)$ of positive integers such that $a+b<n$ and such that $gcd(a,b,n)=1$?
I know that the number of positive integer $a$ such that $gcd(a,n)=1$ is just $varphi(n)$. Maybe we can express the answer for my question above in terms of $varphi(n)$ and other arithmetic functions.
elementary-number-theory arithmetic-functions
asked Jul 17 at 17:07
raja.damanik
518
1
Where does this problem arise?
– saulspatz
Jul 17 at 17:19
In studying to count the number of positive integer solutions of some algebraic equations. Might be not a very fruitful direction of research, but for some cases, it gives a nice alternative proof of some fun facts about arithmetic functions.
– raja.damanik
Jul 17 at 23:25
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Let $n$ be a positive integer.
What is the number of pairs $(a,b)$ of positive integers such that $a+b<n$ and such that $gcd(a,b,n)=1$?
I know that the number of positive integer $a$ such that $gcd(a,n)=1$ is just $varphi(n)$. Maybe we can express the answer for my question above in terms of $varphi(n)$ and other arithmetic functions.
elementary-number-theory arithmetic-functions
asked Jul 17 at 17:07
raja.damanik
518
Let $n$ be a positive integer.
What is the number of pairs $(a,b)$ of positive integers such that $a+b<n$ and such that $gcd(a,b,n)=1$?
I know that the number of positive integer $a$ such that $gcd(a,n)=1$ is just $varphi(n)$. Maybe we can express the answer for my question above in terms of $varphi(n)$ and other arithmetic functions.
elementary-number-theory arithmetic-functions
asked Jul 17 at 17:07
raja.damanik
518
asked Jul 17 at 17:07
raja.damanik
518
asked Jul 17 at 17:07
raja.damanik
518
asked Jul 17 at 17:07
raja.damanik
518
518
1
Where does this problem arise?
– saulspatz
Jul 17 at 17:19
In studying to count the number of positive integer solutions of some algebraic equations. Might be not a very fruitful direction of research, but for some cases, it gives a nice alternative proof of some fun facts about arithmetic functions.
– raja.damanik
Jul 17 at 23:25
add a comment |Â
1
Where does this problem arise?
– saulspatz
Jul 17 at 17:19
In studying to count the number of positive integer solutions of some algebraic equations. Might be not a very fruitful direction of research, but for some cases, it gives a nice alternative proof of some fun facts about arithmetic functions.
– raja.damanik
Jul 17 at 23:25
1
1
Where does this problem arise?
– saulspatz
Jul 17 at 17:19
Where does this problem arise?
– saulspatz
Jul 17 at 17:19
In studying to count the number of positive integer solutions of some algebraic equations. Might be not a very fruitful direction of research, but for some cases, it gives a nice alternative proof of some fun facts about arithmetic functions.
– raja.damanik
Jul 17 at 23:25
In studying to count the number of positive integer solutions of some algebraic equations. Might be not a very fruitful direction of research, but for some cases, it gives a nice alternative proof of some fun facts about arithmetic functions.
– raja.damanik
Jul 17 at 23:25
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
This is A000741 the number of compositions of $n$ into $3$ ordered relatively prime parts. Write $c=n-a-b,$ so that $(a,b,c)$ is a composition of $n$. Some of the scripts given on OEIS seem to relate to the divisor function, but I don't know any of the languages, so I can't be sure.
answered Jul 18 at 1:15
saulspatz
10.7k21323
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
This is A000741 the number of compositions of $n$ into $3$ ordered relatively prime parts. Write $c=n-a-b,$ so that $(a,b,c)$ is a composition of $n$. Some of the scripts given on OEIS seem to relate to the divisor function, but I don't know any of the languages, so I can't be sure.
answered Jul 18 at 1:15
saulspatz
10.7k21323
add a comment |Â
up vote
1
down vote
This is A000741 the number of compositions of $n$ into $3$ ordered relatively prime parts. Write $c=n-a-b,$ so that $(a,b,c)$ is a composition of $n$. Some of the scripts given on OEIS seem to relate to the divisor function, but I don't know any of the languages, so I can't be sure.
answered Jul 18 at 1:15
saulspatz
10.7k21323
add a comment |Â
up vote
1
down vote
up vote
1
down vote
This is A000741 the number of compositions of $n$ into $3$ ordered relatively prime parts. Write $c=n-a-b,$ so that $(a,b,c)$ is a composition of $n$. Some of the scripts given on OEIS seem to relate to the divisor function, but I don't know any of the languages, so I can't be sure.
answered Jul 18 at 1:15
saulspatz
10.7k21323
This is A000741 the number of compositions of $n$ into $3$ ordered relatively prime parts. Write $c=n-a-b,$ so that $(a,b,c)$ is a composition of $n$. Some of the scripts given on OEIS seem to relate to the divisor function, but I don't know any of the languages, so I can't be sure.
answered Jul 18 at 1:15
saulspatz
10.7k21323
answered Jul 18 at 1:15
saulspatz
10.7k21323
answered Jul 18 at 1:15
saulspatz
10.7k21323
answered Jul 18 at 1:15
saulspatz
10.7k21323
10.7k21323
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2854721%2fnumber-of-pairs-a-b-such-that-abn-and-such-that-gcda-b-n-1%23new-answer', 'question_page');
);
Post as a guest
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
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
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
1
Where does this problem arise?
– saulspatz
Jul 17 at 17:19
In studying to count the number of positive integer solutions of some algebraic equations. Might be not a very fruitful direction of research, but for some cases, it gives a nice alternative proof of some fun facts about arithmetic functions.
– raja.damanik
Jul 17 at 23:25