Understanding the Euler function
It should be very basic and simple question related to the Euler function $phi$. If I would like to calculate for example $phi(100)$ I saw that we can write it as $phi(2^2cdot 5^2)$. Also I saw a theorem that says $phi(acdot b) = phi(a)cdot phi(b)$ if $a,b$ are prime numbers. So we get $phi(100)=phi(2)phi(2)phi(5)phi(5)=1cdot 1cdot 4cdot 4=16$, But it isn't true because I know that $phi(100)=40$. What is the right why to dismantle $100$ so we can use the euler function?
group-theory
edited Nov 24 at 23:02
Bernard
117k637110
asked Nov 24 at 22:11
vesii
635
add a comment |
It should be very basic and simple question related to the Euler function $phi$. If I would like to calculate for example $phi(100)$ I saw that we can write it as $phi(2^2cdot 5^2)$. Also I saw a theorem that says $phi(acdot b) = phi(a)cdot phi(b)$ if $a,b$ are prime numbers. So we get $phi(100)=phi(2)phi(2)phi(5)phi(5)=1cdot 1cdot 4cdot 4=16$, But it isn't true because I know that $phi(100)=40$. What is the right why to dismantle $100$ so we can use the euler function?
group-theory
edited Nov 24 at 23:02
Bernard
117k637110
asked Nov 24 at 22:11
vesii
635
3
$phi(acdot b) = phi(a)cdot phi(b)$ is true when $a,b$ are coprime.
– Eclipse Sun
Nov 24 at 22:12
1
$phi(acdot b) = phi(a)cdot phi(b)$ if $a,b$ are relatively prime, so $phi(100)=phi(4)phi(25)$
– saulspatz
Nov 24 at 22:13
add a comment |
It should be very basic and simple question related to the Euler function $phi$. If I would like to calculate for example $phi(100)$ I saw that we can write it as $phi(2^2cdot 5^2)$. Also I saw a theorem that says $phi(acdot b) = phi(a)cdot phi(b)$ if $a,b$ are prime numbers. So we get $phi(100)=phi(2)phi(2)phi(5)phi(5)=1cdot 1cdot 4cdot 4=16$, But it isn't true because I know that $phi(100)=40$. What is the right why to dismantle $100$ so we can use the euler function?
group-theory
edited Nov 24 at 23:02
Bernard
117k637110
asked Nov 24 at 22:11
vesii
635
It should be very basic and simple question related to the Euler function $phi$. If I would like to calculate for example $phi(100)$ I saw that we can write it as $phi(2^2cdot 5^2)$. Also I saw a theorem that says $phi(acdot b) = phi(a)cdot phi(b)$ if $a,b$ are prime numbers. So we get $phi(100)=phi(2)phi(2)phi(5)phi(5)=1cdot 1cdot 4cdot 4=16$, But it isn't true because I know that $phi(100)=40$. What is the right why to dismantle $100$ so we can use the euler function?
group-theory
group-theory
edited Nov 24 at 23:02
Bernard
117k637110
asked Nov 24 at 22:11
vesii
635
edited Nov 24 at 23:02
Bernard
117k637110
asked Nov 24 at 22:11
vesii
635
edited Nov 24 at 23:02
Bernard
117k637110
edited Nov 24 at 23:02
Bernard
117k637110
edited Nov 24 at 23:02
Bernard
117k637110
117k637110
asked Nov 24 at 22:11
vesii
635
asked Nov 24 at 22:11
vesii
635
asked Nov 24 at 22:11
vesii
635
635
3
$phi(acdot b) = phi(a)cdot phi(b)$ is true when $a,b$ are coprime.
– Eclipse Sun
Nov 24 at 22:12
1
$phi(acdot b) = phi(a)cdot phi(b)$ if $a,b$ are relatively prime, so $phi(100)=phi(4)phi(25)$
– saulspatz
Nov 24 at 22:13
add a comment |
3
$phi(acdot b) = phi(a)cdot phi(b)$ is true when $a,b$ are coprime.
– Eclipse Sun
Nov 24 at 22:12
1
$phi(acdot b) = phi(a)cdot phi(b)$ if $a,b$ are relatively prime, so $phi(100)=phi(4)phi(25)$
– saulspatz
Nov 24 at 22:13
3
3
$phi(acdot b) = phi(a)cdot phi(b)$ is true when $a,b$ are coprime.
– Eclipse Sun
Nov 24 at 22:12
$phi(acdot b) = phi(a)cdot phi(b)$ is true when $a,b$ are coprime.
– Eclipse Sun
Nov 24 at 22:12
1
1
$phi(acdot b) = phi(a)cdot phi(b)$ if $a,b$ are relatively prime, so $phi(100)=phi(4)phi(25)$
– saulspatz
Nov 24 at 22:13
$phi(acdot b) = phi(a)cdot phi(b)$ if $a,b$ are relatively prime, so $phi(100)=phi(4)phi(25)$
– saulspatz
Nov 24 at 22:13
add a comment |
2 Answers
2
active
oldest
votes
We write $100$ as $2^2times5^2$. Then, since $gcd(2^2,5^2)=1$,$$phi(2^2times5^2)=phi(2^2)timesphi(5^2).$$And, for any prime $p$, $phi(p^n)=p^n-p^{n-1}=left(1-frac1pright)p^n$. So, $phi(2^2)=2$ and $phi(5^2)=20$. Therefore, $phi(100)=2times20=40$.
answered Nov 24 at 22:15
José Carlos Santos
148k22117218
add a comment |
$phi(100) = phi(5^2 . 2^2) = phi(2^2) phi(5^2) = 2 times (25-20) = 40$
Recall that:
$phi(ab) = phi(a)phi(b) iff a$ and $b$ are coprime i.e $gcd(a,b) = 1$.
$phi(p^a) = p^{a-1}(p-1)$.
answered Nov 24 at 22:16
Maged Saeed
847316
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%2f3012156%2funderstanding-the-euler-function%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
We write $100$ as $2^2times5^2$. Then, since $gcd(2^2,5^2)=1$,$$phi(2^2times5^2)=phi(2^2)timesphi(5^2).$$And, for any prime $p$, $phi(p^n)=p^n-p^{n-1}=left(1-frac1pright)p^n$. So, $phi(2^2)=2$ and $phi(5^2)=20$. Therefore, $phi(100)=2times20=40$.
answered Nov 24 at 22:15
José Carlos Santos
148k22117218
add a comment |
We write $100$ as $2^2times5^2$. Then, since $gcd(2^2,5^2)=1$,$$phi(2^2times5^2)=phi(2^2)timesphi(5^2).$$And, for any prime $p$, $phi(p^n)=p^n-p^{n-1}=left(1-frac1pright)p^n$. So, $phi(2^2)=2$ and $phi(5^2)=20$. Therefore, $phi(100)=2times20=40$.
answered Nov 24 at 22:15
José Carlos Santos
148k22117218
add a comment |
We write $100$ as $2^2times5^2$. Then, since $gcd(2^2,5^2)=1$,$$phi(2^2times5^2)=phi(2^2)timesphi(5^2).$$And, for any prime $p$, $phi(p^n)=p^n-p^{n-1}=left(1-frac1pright)p^n$. So, $phi(2^2)=2$ and $phi(5^2)=20$. Therefore, $phi(100)=2times20=40$.
answered Nov 24 at 22:15
José Carlos Santos
148k22117218
We write $100$ as $2^2times5^2$. Then, since $gcd(2^2,5^2)=1$,$$phi(2^2times5^2)=phi(2^2)timesphi(5^2).$$And, for any prime $p$, $phi(p^n)=p^n-p^{n-1}=left(1-frac1pright)p^n$. So, $phi(2^2)=2$ and $phi(5^2)=20$. Therefore, $phi(100)=2times20=40$.
answered Nov 24 at 22:15
José Carlos Santos
148k22117218
answered Nov 24 at 22:15
José Carlos Santos
148k22117218
answered Nov 24 at 22:15
José Carlos Santos
148k22117218
answered Nov 24 at 22:15
José Carlos Santos
148k22117218
148k22117218
add a comment |
add a comment |
$phi(100) = phi(5^2 . 2^2) = phi(2^2) phi(5^2) = 2 times (25-20) = 40$
Recall that:
$phi(ab) = phi(a)phi(b) iff a$ and $b$ are coprime i.e $gcd(a,b) = 1$.
$phi(p^a) = p^{a-1}(p-1)$.
answered Nov 24 at 22:16
Maged Saeed
847316
add a comment |
$phi(100) = phi(5^2 . 2^2) = phi(2^2) phi(5^2) = 2 times (25-20) = 40$
Recall that:
$phi(ab) = phi(a)phi(b) iff a$ and $b$ are coprime i.e $gcd(a,b) = 1$.
$phi(p^a) = p^{a-1}(p-1)$.
answered Nov 24 at 22:16
Maged Saeed
847316
add a comment |
$phi(100) = phi(5^2 . 2^2) = phi(2^2) phi(5^2) = 2 times (25-20) = 40$
Recall that:
$phi(ab) = phi(a)phi(b) iff a$ and $b$ are coprime i.e $gcd(a,b) = 1$.
$phi(p^a) = p^{a-1}(p-1)$.
answered Nov 24 at 22:16
Maged Saeed
847316
$phi(100) = phi(5^2 . 2^2) = phi(2^2) phi(5^2) = 2 times (25-20) = 40$
Recall that:
$phi(ab) = phi(a)phi(b) iff a$ and $b$ are coprime i.e $gcd(a,b) = 1$.
$phi(p^a) = p^{a-1}(p-1)$.
answered Nov 24 at 22:16
Maged Saeed
847316
edited Nov 24 at 22:23
answered Nov 24 at 22:16
Maged Saeed
847316
answered Nov 24 at 22:16
Maged Saeed
847316
answered Nov 24 at 22:16
Maged Saeed
847316
847316
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%2f3012156%2funderstanding-the-euler-function%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
3
$phi(acdot b) = phi(a)cdot phi(b)$ is true when $a,b$ are coprime.
– Eclipse Sun
Nov 24 at 22:12
1
$phi(acdot b) = phi(a)cdot phi(b)$ if $a,b$ are relatively prime, so $phi(100)=phi(4)phi(25)$
– saulspatz
Nov 24 at 22:13