The totient of a factor of a number divides the totient of the number.
Given any number and one of its factors, how can you show that the totient of the factor divides the totient of the original number?
number-theory elementary-number-theory
asked Dec 9 at 0:20
Arthur Chong
62
add a comment |
Given any number and one of its factors, how can you show that the totient of the factor divides the totient of the original number?
number-theory elementary-number-theory
asked Dec 9 at 0:20
Arthur Chong
62
What do you mean $phi(mn)=phi(m)+phi(n)$?
– Hagen von Eitzen
Dec 9 at 0:22
I know that the totient of a number is equal to the sum of the totient of each of its factors so could we not make that statement since mn can be factored into m and n?
– Arthur Chong
Dec 9 at 0:58
add a comment |
Given any number and one of its factors, how can you show that the totient of the factor divides the totient of the original number?
number-theory elementary-number-theory
asked Dec 9 at 0:20
Arthur Chong
62
Given any number and one of its factors, how can you show that the totient of the factor divides the totient of the original number?
number-theory elementary-number-theory
number-theory elementary-number-theory
asked Dec 9 at 0:20
Arthur Chong
62
asked Dec 9 at 0:20
Arthur Chong
62
edited Dec 10 at 0:27
asked Dec 9 at 0:20
Arthur Chong
62
asked Dec 9 at 0:20
Arthur Chong
62
asked Dec 9 at 0:20
Arthur Chong
62
62
What do you mean $phi(mn)=phi(m)+phi(n)$?
– Hagen von Eitzen
Dec 9 at 0:22
I know that the totient of a number is equal to the sum of the totient of each of its factors so could we not make that statement since mn can be factored into m and n?
– Arthur Chong
Dec 9 at 0:58
add a comment |
What do you mean $phi(mn)=phi(m)+phi(n)$?
– Hagen von Eitzen
Dec 9 at 0:22
I know that the totient of a number is equal to the sum of the totient of each of its factors so could we not make that statement since mn can be factored into m and n?
– Arthur Chong
Dec 9 at 0:58
What do you mean $phi(mn)=phi(m)+phi(n)$?
– Hagen von Eitzen
Dec 9 at 0:22
What do you mean $phi(mn)=phi(m)+phi(n)$?
– Hagen von Eitzen
Dec 9 at 0:22
I know that the totient of a number is equal to the sum of the totient of each of its factors so could we not make that statement since mn can be factored into m and n?
– Arthur Chong
Dec 9 at 0:58
I know that the totient of a number is equal to the sum of the totient of each of its factors so could we not make that statement since mn can be factored into m and n?
– Arthur Chong
Dec 9 at 0:58
add a comment |
2 Answers
2
active
oldest
votes
- If $pmid n$ then $phi(pn)=pphi(n)$.
- If $pnmid n$ then $phi(pn)=(p-1)phi(n)$.
answered Dec 9 at 0:23
Hagen von Eitzen
276k21268495
How would I exactly use this? I don't have that either m or n are prime.
– Arthur Chong
Dec 9 at 0:59
add a comment |
Expanding on Hagen's answer: Let $mmid n$, we need to show that $phi(m)midphi(n)$. If $m$ is prime then we are done, since $phi(pm)=pphi(m)$. If $m$ is not prime, then it can be decomposed into a product of primes, say $prod p^alpha$. Then
$$phi(m)=phi(prod p^alpha)=prod p^{alpha-1}prod(p-1).$$
Now, $phi(n)$ can be expressed as this product times the totient function of all the extra prime factors $n$ has that is not in $m$. Think of this as because we have "taken out" all the prime powers of $m$ to get that product, and we can do the same thing for $n$ and still have "leftovers". The conclusion follows.
answered Dec 10 at 0:41
YiFan
2,4041421
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
});
}
});
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%2f3031848%2fthe-totient-of-a-factor-of-a-number-divides-the-totient-of-the-number%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
- If $pmid n$ then $phi(pn)=pphi(n)$.
- If $pnmid n$ then $phi(pn)=(p-1)phi(n)$.
answered Dec 9 at 0:23
Hagen von Eitzen
276k21268495
How would I exactly use this? I don't have that either m or n are prime.
– Arthur Chong
Dec 9 at 0:59
add a comment |
- If $pmid n$ then $phi(pn)=pphi(n)$.
- If $pnmid n$ then $phi(pn)=(p-1)phi(n)$.
answered Dec 9 at 0:23
Hagen von Eitzen
276k21268495
How would I exactly use this? I don't have that either m or n are prime.
– Arthur Chong
Dec 9 at 0:59
add a comment |
- If $pmid n$ then $phi(pn)=pphi(n)$.
- If $pnmid n$ then $phi(pn)=(p-1)phi(n)$.
answered Dec 9 at 0:23
Hagen von Eitzen
276k21268495
- If $pmid n$ then $phi(pn)=pphi(n)$.
- If $pnmid n$ then $phi(pn)=(p-1)phi(n)$.
answered Dec 9 at 0:23
Hagen von Eitzen
276k21268495
answered Dec 9 at 0:23
Hagen von Eitzen
276k21268495
answered Dec 9 at 0:23
Hagen von Eitzen
276k21268495
answered Dec 9 at 0:23
Hagen von Eitzen
276k21268495
276k21268495
How would I exactly use this? I don't have that either m or n are prime.
– Arthur Chong
Dec 9 at 0:59
add a comment |
How would I exactly use this? I don't have that either m or n are prime.
– Arthur Chong
Dec 9 at 0:59
How would I exactly use this? I don't have that either m or n are prime.
– Arthur Chong
Dec 9 at 0:59
How would I exactly use this? I don't have that either m or n are prime.
– Arthur Chong
Dec 9 at 0:59
add a comment |
Expanding on Hagen's answer: Let $mmid n$, we need to show that $phi(m)midphi(n)$. If $m$ is prime then we are done, since $phi(pm)=pphi(m)$. If $m$ is not prime, then it can be decomposed into a product of primes, say $prod p^alpha$. Then
$$phi(m)=phi(prod p^alpha)=prod p^{alpha-1}prod(p-1).$$
Now, $phi(n)$ can be expressed as this product times the totient function of all the extra prime factors $n$ has that is not in $m$. Think of this as because we have "taken out" all the prime powers of $m$ to get that product, and we can do the same thing for $n$ and still have "leftovers". The conclusion follows.
answered Dec 10 at 0:41
YiFan
2,4041421
add a comment |
Expanding on Hagen's answer: Let $mmid n$, we need to show that $phi(m)midphi(n)$. If $m$ is prime then we are done, since $phi(pm)=pphi(m)$. If $m$ is not prime, then it can be decomposed into a product of primes, say $prod p^alpha$. Then
$$phi(m)=phi(prod p^alpha)=prod p^{alpha-1}prod(p-1).$$
Now, $phi(n)$ can be expressed as this product times the totient function of all the extra prime factors $n$ has that is not in $m$. Think of this as because we have "taken out" all the prime powers of $m$ to get that product, and we can do the same thing for $n$ and still have "leftovers". The conclusion follows.
answered Dec 10 at 0:41
YiFan
2,4041421
add a comment |
Expanding on Hagen's answer: Let $mmid n$, we need to show that $phi(m)midphi(n)$. If $m$ is prime then we are done, since $phi(pm)=pphi(m)$. If $m$ is not prime, then it can be decomposed into a product of primes, say $prod p^alpha$. Then
$$phi(m)=phi(prod p^alpha)=prod p^{alpha-1}prod(p-1).$$
Now, $phi(n)$ can be expressed as this product times the totient function of all the extra prime factors $n$ has that is not in $m$. Think of this as because we have "taken out" all the prime powers of $m$ to get that product, and we can do the same thing for $n$ and still have "leftovers". The conclusion follows.
answered Dec 10 at 0:41
YiFan
2,4041421
Expanding on Hagen's answer: Let $mmid n$, we need to show that $phi(m)midphi(n)$. If $m$ is prime then we are done, since $phi(pm)=pphi(m)$. If $m$ is not prime, then it can be decomposed into a product of primes, say $prod p^alpha$. Then
$$phi(m)=phi(prod p^alpha)=prod p^{alpha-1}prod(p-1).$$
Now, $phi(n)$ can be expressed as this product times the totient function of all the extra prime factors $n$ has that is not in $m$. Think of this as because we have "taken out" all the prime powers of $m$ to get that product, and we can do the same thing for $n$ and still have "leftovers". The conclusion follows.
answered Dec 10 at 0:41
YiFan
2,4041421
answered Dec 10 at 0:41
YiFan
2,4041421
answered Dec 10 at 0:41
YiFan
2,4041421
answered Dec 10 at 0:41
YiFan
2,4041421
2,4041421
add a comment |
add a comment |
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%2f3031848%2fthe-totient-of-a-factor-of-a-number-divides-the-totient-of-the-number%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
What do you mean $phi(mn)=phi(m)+phi(n)$?
– Hagen von Eitzen
Dec 9 at 0:22
I know that the totient of a number is equal to the sum of the totient of each of its factors so could we not make that statement since mn can be factored into m and n?
– Arthur Chong
Dec 9 at 0:58