The totient of a factor of a number divides the totient of the number.
$begingroup$
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 '18 at 0:20
Arthur ChongArthur Chong
62
$endgroup$
add a comment |
$begingroup$
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 '18 at 0:20
Arthur ChongArthur Chong
62
$endgroup$
$begingroup$
What do you mean $phi(mn)=phi(m)+phi(n)$?
$endgroup$
– Hagen von Eitzen
Dec 9 '18 at 0:22
$begingroup$
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?
$endgroup$
– Arthur Chong
Dec 9 '18 at 0:58
add a comment |
$begingroup$
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 '18 at 0:20
Arthur ChongArthur Chong
62
$endgroup$
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 '18 at 0:20
Arthur ChongArthur Chong
62
asked Dec 9 '18 at 0:20
Arthur ChongArthur Chong
62
edited Dec 10 '18 at 0:27
Arthur Chong
asked Dec 9 '18 at 0:20
Arthur ChongArthur Chong
62
asked Dec 9 '18 at 0:20
Arthur ChongArthur Chong
62
asked Dec 9 '18 at 0:20
Arthur ChongArthur Chong
62
62
$begingroup$
What do you mean $phi(mn)=phi(m)+phi(n)$?
$endgroup$
– Hagen von Eitzen
Dec 9 '18 at 0:22
$begingroup$
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?
$endgroup$
– Arthur Chong
Dec 9 '18 at 0:58
add a comment |
$begingroup$
What do you mean $phi(mn)=phi(m)+phi(n)$?
$endgroup$
– Hagen von Eitzen
Dec 9 '18 at 0:22
$begingroup$
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?
$endgroup$
– Arthur Chong
Dec 9 '18 at 0:58
$begingroup$
What do you mean $phi(mn)=phi(m)+phi(n)$?
$endgroup$
– Hagen von Eitzen
Dec 9 '18 at 0:22
$begingroup$
What do you mean $phi(mn)=phi(m)+phi(n)$?
$endgroup$
– Hagen von Eitzen
Dec 9 '18 at 0:22
$begingroup$
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?
$endgroup$
– Arthur Chong
Dec 9 '18 at 0:58
$begingroup$
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?
$endgroup$
– Arthur Chong
Dec 9 '18 at 0:58
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
- If $pmid n$ then $phi(pn)=pphi(n)$.
- If $pnmid n$ then $phi(pn)=(p-1)phi(n)$.
answered Dec 9 '18 at 0:23
Hagen von EitzenHagen von Eitzen
277k22269496
$endgroup$
$begingroup$
How would I exactly use this? I don't have that either m or n are prime.
$endgroup$
– Arthur Chong
Dec 9 '18 at 0:59
add a comment |
$begingroup$
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 '18 at 0:41
YiFanYiFan
2,7641422
$endgroup$
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
$begingroup$
- If $pmid n$ then $phi(pn)=pphi(n)$.
- If $pnmid n$ then $phi(pn)=(p-1)phi(n)$.
answered Dec 9 '18 at 0:23
Hagen von EitzenHagen von Eitzen
277k22269496
$endgroup$
$begingroup$
How would I exactly use this? I don't have that either m or n are prime.
$endgroup$
– Arthur Chong
Dec 9 '18 at 0:59
add a comment |
$begingroup$
- If $pmid n$ then $phi(pn)=pphi(n)$.
- If $pnmid n$ then $phi(pn)=(p-1)phi(n)$.
answered Dec 9 '18 at 0:23
Hagen von EitzenHagen von Eitzen
277k22269496
$endgroup$
$begingroup$
How would I exactly use this? I don't have that either m or n are prime.
$endgroup$
– Arthur Chong
Dec 9 '18 at 0:59
add a comment |
$begingroup$
- If $pmid n$ then $phi(pn)=pphi(n)$.
- If $pnmid n$ then $phi(pn)=(p-1)phi(n)$.
answered Dec 9 '18 at 0:23
Hagen von EitzenHagen von Eitzen
277k22269496
$endgroup$
- If $pmid n$ then $phi(pn)=pphi(n)$.
- If $pnmid n$ then $phi(pn)=(p-1)phi(n)$.
answered Dec 9 '18 at 0:23
Hagen von EitzenHagen von Eitzen
277k22269496
answered Dec 9 '18 at 0:23
Hagen von EitzenHagen von Eitzen
277k22269496
answered Dec 9 '18 at 0:23
Hagen von EitzenHagen von Eitzen
277k22269496
answered Dec 9 '18 at 0:23
Hagen von EitzenHagen von Eitzen
277k22269496
277k22269496
$begingroup$
How would I exactly use this? I don't have that either m or n are prime.
$endgroup$
– Arthur Chong
Dec 9 '18 at 0:59
add a comment |
$begingroup$
How would I exactly use this? I don't have that either m or n are prime.
$endgroup$
– Arthur Chong
Dec 9 '18 at 0:59
$begingroup$
How would I exactly use this? I don't have that either m or n are prime.
$endgroup$
– Arthur Chong
Dec 9 '18 at 0:59
$begingroup$
How would I exactly use this? I don't have that either m or n are prime.
$endgroup$
– Arthur Chong
Dec 9 '18 at 0:59
add a comment |
$begingroup$
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 '18 at 0:41
YiFanYiFan
2,7641422
$endgroup$
add a comment |
$begingroup$
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 '18 at 0:41
YiFanYiFan
2,7641422
$endgroup$
add a comment |
$begingroup$
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 '18 at 0:41
YiFanYiFan
2,7641422
$endgroup$
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 '18 at 0:41
YiFanYiFan
2,7641422
answered Dec 10 '18 at 0:41
YiFanYiFan
2,7641422
answered Dec 10 '18 at 0:41
YiFanYiFan
2,7641422
answered Dec 10 '18 at 0:41
YiFanYiFan
2,7641422
2,7641422
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.
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
$begingroup$
What do you mean $phi(mn)=phi(m)+phi(n)$?
$endgroup$
– Hagen von Eitzen
Dec 9 '18 at 0:22
$begingroup$
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?
$endgroup$
– Arthur Chong
Dec 9 '18 at 0:58