Are there exactly $N$ different irreductible fractions less or equal than $1$ with denominator divisor of $N$?

Clash Royale CLAN TAG#URR8PPP

up vote
1
down vote

favorite

Solving an exercise, I saw some cases that this was true, like $N=6$, where the $6$ fractions are $1, 1/2, 1/3, 2/3, 1/6, 5/6$, and then intuited it was always true. I guess we can prove it writing the prime factorization of $N$: $a^Ab^B...k^K$, and using the numbers of divisors, $(A+1)(B+1)...(K+1)$.

number-theory

share|cite|improve this question

asked Jul 31 at 2:51

Alexandre Tourinho

1305

add a comment | 

up vote
1
down vote

favorite

Solving an exercise, I saw some cases that this was true, like $N=6$, where the $6$ fractions are $1, 1/2, 1/3, 2/3, 1/6, 5/6$, and then intuited it was always true. I guess we can prove it writing the prime factorization of $N$: $a^Ab^B...k^K$, and using the numbers of divisors, $(A+1)(B+1)...(K+1)$.

number-theory

share|cite|improve this question

asked Jul 31 at 2:51

Alexandre Tourinho

1305

add a comment | 

up vote
1
down vote

favorite

up vote
1
down vote

favorite

Solving an exercise, I saw some cases that this was true, like $N=6$, where the $6$ fractions are $1, 1/2, 1/3, 2/3, 1/6, 5/6$, and then intuited it was always true. I guess we can prove it writing the prime factorization of $N$: $a^Ab^B...k^K$, and using the numbers of divisors, $(A+1)(B+1)...(K+1)$.

number-theory

share|cite|improve this question

asked Jul 31 at 2:51

Alexandre Tourinho

1305

Solving an exercise, I saw some cases that this was true, like $N=6$, where the $6$ fractions are $1, 1/2, 1/3, 2/3, 1/6, 5/6$, and then intuited it was always true. I guess we can prove it writing the prime factorization of $N$: $a^Ab^B...k^K$, and using the numbers of divisors, $(A+1)(B+1)...(K+1)$.

number-theory

share|cite|improve this question

asked Jul 31 at 2:51

Alexandre Tourinho

1305

share|cite|improve this question

share|cite|improve this question

asked Jul 31 at 2:51

Alexandre Tourinho

1305

asked Jul 31 at 2:51

Alexandre Tourinho

1305

asked Jul 31 at 2:51

Alexandre Tourinho

1305

1305

add a comment | 

add a comment | 

2 Answers
2

active

oldest

votes

up vote
3
down vote

Different viewpoint: the fractions with denominator $d$ that are already in lowest terms have numerator coprime to $d,$ and no larger than $d$ itself. The count of those numerators is the Euler totient $phi(d)$

There is then a fairly easy number theory fact using "multiplicative" functions,
$$ sum_d ; phi(d) = n $$

This identity has appeared many times as a question... Is there a direct, elementary proof of $n = sum_k phi(k)$?

share|cite|improve this answer

edited Jul 31 at 3:40

answered Jul 31 at 3:11

Will Jagy

96.8k594195

add a comment | 

up vote
1
down vote

Yes. All fractions in $(0,1]$ with denominators as divisors of $N$ must equal $k/N$ for some integer $1leq kleq N$, and each of those reduce to exactly one irreducible fraction.

share|cite|improve this answer

answered Jul 31 at 2:56

Carl Schildkraut

8,23711238

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',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

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

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2867599%2fare-there-exactly-n-different-irreductible-fractions-less-or-equal-than-1-wi%23new-answer', 'question_page');

);

Post as a guest

Name Email

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
3
down vote

Different viewpoint: the fractions with denominator $d$ that are already in lowest terms have numerator coprime to $d,$ and no larger than $d$ itself. The count of those numerators is the Euler totient $phi(d)$

There is then a fairly easy number theory fact using "multiplicative" functions,
$$ sum_d ; phi(d) = n $$

This identity has appeared many times as a question... Is there a direct, elementary proof of $n = sum_k phi(k)$?

share|cite|improve this answer

edited Jul 31 at 3:40

answered Jul 31 at 3:11

Will Jagy

96.8k594195

add a comment | 

up vote
3
down vote

Different viewpoint: the fractions with denominator $d$ that are already in lowest terms have numerator coprime to $d,$ and no larger than $d$ itself. The count of those numerators is the Euler totient $phi(d)$

There is then a fairly easy number theory fact using "multiplicative" functions,
$$ sum_d ; phi(d) = n $$

This identity has appeared many times as a question... Is there a direct, elementary proof of $n = sum_k phi(k)$?

share|cite|improve this answer

edited Jul 31 at 3:40

answered Jul 31 at 3:11

Will Jagy

96.8k594195

add a comment | 

up vote
3
down vote

up vote
3
down vote

Different viewpoint: the fractions with denominator $d$ that are already in lowest terms have numerator coprime to $d,$ and no larger than $d$ itself. The count of those numerators is the Euler totient $phi(d)$

There is then a fairly easy number theory fact using "multiplicative" functions,
$$ sum_d ; phi(d) = n $$

This identity has appeared many times as a question... Is there a direct, elementary proof of $n = sum_k phi(k)$?

share|cite|improve this answer

edited Jul 31 at 3:40

answered Jul 31 at 3:11

Will Jagy

96.8k594195

Different viewpoint: the fractions with denominator $d$ that are already in lowest terms have numerator coprime to $d,$ and no larger than $d$ itself. The count of those numerators is the Euler totient $phi(d)$

There is then a fairly easy number theory fact using "multiplicative" functions,
$$ sum_d ; phi(d) = n $$

This identity has appeared many times as a question... Is there a direct, elementary proof of $n = sum_k phi(k)$?

share|cite|improve this answer

edited Jul 31 at 3:40

answered Jul 31 at 3:11

Will Jagy

96.8k594195

share|cite|improve this answer

share|cite|improve this answer

edited Jul 31 at 3:40

edited Jul 31 at 3:40

edited Jul 31 at 3:40

answered Jul 31 at 3:11

Will Jagy

96.8k594195

answered Jul 31 at 3:11

Will Jagy

96.8k594195

answered Jul 31 at 3:11

Will Jagy

96.8k594195

96.8k594195

add a comment | 

add a comment | 

up vote
1
down vote

Yes. All fractions in $(0,1]$ with denominators as divisors of $N$ must equal $k/N$ for some integer $1leq kleq N$, and each of those reduce to exactly one irreducible fraction.

share|cite|improve this answer

answered Jul 31 at 2:56

Carl Schildkraut

8,23711238

add a comment | 

up vote
1
down vote

Yes. All fractions in $(0,1]$ with denominators as divisors of $N$ must equal $k/N$ for some integer $1leq kleq N$, and each of those reduce to exactly one irreducible fraction.

share|cite|improve this answer

answered Jul 31 at 2:56

Carl Schildkraut

8,23711238

add a comment | 

up vote
1
down vote

up vote
1
down vote

Yes. All fractions in $(0,1]$ with denominators as divisors of $N$ must equal $k/N$ for some integer $1leq kleq N$, and each of those reduce to exactly one irreducible fraction.

share|cite|improve this answer

answered Jul 31 at 2:56

Carl Schildkraut

8,23711238

Yes. All fractions in $(0,1]$ with denominators as divisors of $N$ must equal $k/N$ for some integer $1leq kleq N$, and each of those reduce to exactly one irreducible fraction.

share|cite|improve this answer

answered Jul 31 at 2:56

Carl Schildkraut

8,23711238

share|cite|improve this answer

share|cite|improve this answer

answered Jul 31 at 2:56

Carl Schildkraut

8,23711238

answered Jul 31 at 2:56

Carl Schildkraut

8,23711238

answered Jul 31 at 2:56

Carl Schildkraut

8,23711238

8,23711238

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

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

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2867599%2fare-there-exactly-n-different-irreductible-fractions-less-or-equal-than-1-wi%23new-answer', 'question_page');

);

Post as a guest

Name Email

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

Name Email

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

Name Email

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

Name Email

Name Email

Name

Email

Name Email

Name

Email