Direct passage from $n$ prime to $n$ non-prime in Euler Totient Function $Phi$
$begingroup$
I wish to derive, for a proof, the Euler Totient Function starting from the case $n$ prime to $n$ non-prime.
Let $n$ prime, we know $Phi(n)=n-1$. But what if now I assume $n=p_0^{a_0}p_1^{a_1}...p_r^{a_r}$ and I want to reach $Phi(n)=n prod_{p|n}^{}(1-1/p) $ from there? Like:
$Phi(p_0^{a_0}p_1^{a_1}...p_r^{a_r})=p_0^{a_0}p_1^{a_1}...p_r^{a_r}-1 Rightarrow p_0^{a_0}p_1^{a_1}...p_r^{a_r}(1-1/(p_0^{a_0}p_1^{a_1}...p_r^{a_r}))=?$
Is this kind of approach possible for this formula?
abstract-algebra elementary-number-theory modular-arithmetic totient-function
$endgroup$
add a comment |
$begingroup$
I wish to derive, for a proof, the Euler Totient Function starting from the case $n$ prime to $n$ non-prime.
Let $n$ prime, we know $Phi(n)=n-1$. But what if now I assume $n=p_0^{a_0}p_1^{a_1}...p_r^{a_r}$ and I want to reach $Phi(n)=n prod_{p|n}^{}(1-1/p) $ from there? Like:
$Phi(p_0^{a_0}p_1^{a_1}...p_r^{a_r})=p_0^{a_0}p_1^{a_1}...p_r^{a_r}-1 Rightarrow p_0^{a_0}p_1^{a_1}...p_r^{a_r}(1-1/(p_0^{a_0}p_1^{a_1}...p_r^{a_r}))=?$
Is this kind of approach possible for this formula?
abstract-algebra elementary-number-theory modular-arithmetic totient-function
$endgroup$
3
$begingroup$
The two steps are $phi(p^k) = p^k-p^{k-1}$ and $phi(nm) = phi(n) phi(m)$ whenever $gcd(n,m)=1$ thus $phi(n) = prod_{p^k |n} phi(p^k) = nprod_{p^k |n} frac{phi(p^k) }{p^k}= n prod_{p| n} (1-p^{-1})$
$endgroup$
– reuns
Jan 15 at 8:19
1
$begingroup$
In particular, it is not true that $phi(p_0^{a_0}p_1^{a_1}cdots p_r^{a_r})=p_0^{a_0}p_1^{a_1}cdots p_r^{a_r}-1$ when $p_0^{a_0}p_1^{a_1}cdots p_r^{a_r}$ is not prime.
$endgroup$
– Greg Martin
Jan 15 at 8:28
$begingroup$
So such kind of derivation, as I suppose, it's not possible. Thanks
$endgroup$
– Alessar
Jan 15 at 8:31
$begingroup$
@reuns the symbol "$||$" means for "that divide"?
$endgroup$
– Alessar
Jan 15 at 9:13
1
$begingroup$
$p^k| n$ iff $p^k | n$ and $p^{k+1} nmid n$. In this setting $p$ means (ranging over) the primes and $p^k$ means over the prime powers
$endgroup$
– reuns
Jan 15 at 9:17
add a comment |
$begingroup$
I wish to derive, for a proof, the Euler Totient Function starting from the case $n$ prime to $n$ non-prime.
Let $n$ prime, we know $Phi(n)=n-1$. But what if now I assume $n=p_0^{a_0}p_1^{a_1}...p_r^{a_r}$ and I want to reach $Phi(n)=n prod_{p|n}^{}(1-1/p) $ from there? Like:
$Phi(p_0^{a_0}p_1^{a_1}...p_r^{a_r})=p_0^{a_0}p_1^{a_1}...p_r^{a_r}-1 Rightarrow p_0^{a_0}p_1^{a_1}...p_r^{a_r}(1-1/(p_0^{a_0}p_1^{a_1}...p_r^{a_r}))=?$
Is this kind of approach possible for this formula?
abstract-algebra elementary-number-theory modular-arithmetic totient-function
$endgroup$
I wish to derive, for a proof, the Euler Totient Function starting from the case $n$ prime to $n$ non-prime.
Let $n$ prime, we know $Phi(n)=n-1$. But what if now I assume $n=p_0^{a_0}p_1^{a_1}...p_r^{a_r}$ and I want to reach $Phi(n)=n prod_{p|n}^{}(1-1/p) $ from there? Like:
$Phi(p_0^{a_0}p_1^{a_1}...p_r^{a_r})=p_0^{a_0}p_1^{a_1}...p_r^{a_r}-1 Rightarrow p_0^{a_0}p_1^{a_1}...p_r^{a_r}(1-1/(p_0^{a_0}p_1^{a_1}...p_r^{a_r}))=?$
Is this kind of approach possible for this formula?
abstract-algebra elementary-number-theory modular-arithmetic totient-function
abstract-algebra elementary-number-theory modular-arithmetic totient-function
asked Jan 15 at 8:17
AlessarAlessar
29615
29615
3
$begingroup$
The two steps are $phi(p^k) = p^k-p^{k-1}$ and $phi(nm) = phi(n) phi(m)$ whenever $gcd(n,m)=1$ thus $phi(n) = prod_{p^k |n} phi(p^k) = nprod_{p^k |n} frac{phi(p^k) }{p^k}= n prod_{p| n} (1-p^{-1})$
$endgroup$
– reuns
Jan 15 at 8:19
1
$begingroup$
In particular, it is not true that $phi(p_0^{a_0}p_1^{a_1}cdots p_r^{a_r})=p_0^{a_0}p_1^{a_1}cdots p_r^{a_r}-1$ when $p_0^{a_0}p_1^{a_1}cdots p_r^{a_r}$ is not prime.
$endgroup$
– Greg Martin
Jan 15 at 8:28
$begingroup$
So such kind of derivation, as I suppose, it's not possible. Thanks
$endgroup$
– Alessar
Jan 15 at 8:31
$begingroup$
@reuns the symbol "$||$" means for "that divide"?
$endgroup$
– Alessar
Jan 15 at 9:13
1
$begingroup$
$p^k| n$ iff $p^k | n$ and $p^{k+1} nmid n$. In this setting $p$ means (ranging over) the primes and $p^k$ means over the prime powers
$endgroup$
– reuns
Jan 15 at 9:17
add a comment |
3
$begingroup$
The two steps are $phi(p^k) = p^k-p^{k-1}$ and $phi(nm) = phi(n) phi(m)$ whenever $gcd(n,m)=1$ thus $phi(n) = prod_{p^k |n} phi(p^k) = nprod_{p^k |n} frac{phi(p^k) }{p^k}= n prod_{p| n} (1-p^{-1})$
$endgroup$
– reuns
Jan 15 at 8:19
1
$begingroup$
In particular, it is not true that $phi(p_0^{a_0}p_1^{a_1}cdots p_r^{a_r})=p_0^{a_0}p_1^{a_1}cdots p_r^{a_r}-1$ when $p_0^{a_0}p_1^{a_1}cdots p_r^{a_r}$ is not prime.
$endgroup$
– Greg Martin
Jan 15 at 8:28
$begingroup$
So such kind of derivation, as I suppose, it's not possible. Thanks
$endgroup$
– Alessar
Jan 15 at 8:31
$begingroup$
@reuns the symbol "$||$" means for "that divide"?
$endgroup$
– Alessar
Jan 15 at 9:13
1
$begingroup$
$p^k| n$ iff $p^k | n$ and $p^{k+1} nmid n$. In this setting $p$ means (ranging over) the primes and $p^k$ means over the prime powers
$endgroup$
– reuns
Jan 15 at 9:17
3
3
$begingroup$
The two steps are $phi(p^k) = p^k-p^{k-1}$ and $phi(nm) = phi(n) phi(m)$ whenever $gcd(n,m)=1$ thus $phi(n) = prod_{p^k |n} phi(p^k) = nprod_{p^k |n} frac{phi(p^k) }{p^k}= n prod_{p| n} (1-p^{-1})$
$endgroup$
– reuns
Jan 15 at 8:19
$begingroup$
The two steps are $phi(p^k) = p^k-p^{k-1}$ and $phi(nm) = phi(n) phi(m)$ whenever $gcd(n,m)=1$ thus $phi(n) = prod_{p^k |n} phi(p^k) = nprod_{p^k |n} frac{phi(p^k) }{p^k}= n prod_{p| n} (1-p^{-1})$
$endgroup$
– reuns
Jan 15 at 8:19
1
1
$begingroup$
In particular, it is not true that $phi(p_0^{a_0}p_1^{a_1}cdots p_r^{a_r})=p_0^{a_0}p_1^{a_1}cdots p_r^{a_r}-1$ when $p_0^{a_0}p_1^{a_1}cdots p_r^{a_r}$ is not prime.
$endgroup$
– Greg Martin
Jan 15 at 8:28
$begingroup$
In particular, it is not true that $phi(p_0^{a_0}p_1^{a_1}cdots p_r^{a_r})=p_0^{a_0}p_1^{a_1}cdots p_r^{a_r}-1$ when $p_0^{a_0}p_1^{a_1}cdots p_r^{a_r}$ is not prime.
$endgroup$
– Greg Martin
Jan 15 at 8:28
$begingroup$
So such kind of derivation, as I suppose, it's not possible. Thanks
$endgroup$
– Alessar
Jan 15 at 8:31
$begingroup$
So such kind of derivation, as I suppose, it's not possible. Thanks
$endgroup$
– Alessar
Jan 15 at 8:31
$begingroup$
@reuns the symbol "$||$" means for "that divide"?
$endgroup$
– Alessar
Jan 15 at 9:13
$begingroup$
@reuns the symbol "$||$" means for "that divide"?
$endgroup$
– Alessar
Jan 15 at 9:13
1
1
$begingroup$
$p^k| n$ iff $p^k | n$ and $p^{k+1} nmid n$. In this setting $p$ means (ranging over) the primes and $p^k$ means over the prime powers
$endgroup$
– reuns
Jan 15 at 9:17
$begingroup$
$p^k| n$ iff $p^k | n$ and $p^{k+1} nmid n$. In this setting $p$ means (ranging over) the primes and $p^k$ means over the prime powers
$endgroup$
– reuns
Jan 15 at 9:17
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
To be precise, your "kind" of derivation is not possible. This is because $phi(p_0^{a_0}p_1^{a_1}...p_r^{a_r})neq p_0^{a_0}p_1^{a_1}...p_r^{a_r}-1$.
Think about what the totient function entails: the number of integers less than the input that are coprime with it. Only with prime inputs is this one less than the input.
The totient function, however, does retain two properties, namely as reuns mentioned, that $phi(p^k)=p^k-p^{k-1}$ and $phi(n)phi(m)=phi(mn)$ when $m$ and $n$ are coprime. The proof of these is easily verifiable given a google search.
Thus, we can have a "direct" approach. Since powers of primes are always coprime to one another,
begin{align*}
phi(n)&=phi(p_0^{a_0}p_1^{a_1}...p_r^{a_r})\
&=phi(p_0^{a_0})phi(p_1^{a_1})...phi(p_r^{a_r})\
&=(p_0^{a_0}-p_0^{a_0-1})(p_1^{a_1}-p_1^{a_1-1})...(p_r^{a_r}-p_r^{a_r-1})\
&=p_0^{a_0}(1-1/p_0)p_1^{a_1}(1-1/p_1)...p_r^{a_r}(1-1/p_r)\
&=ndisplaystyleprod_{p|n}(1-1/p).
end{align*}
$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%2f3074184%2fdirect-passage-from-n-prime-to-n-non-prime-in-euler-totient-function-phi%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
To be precise, your "kind" of derivation is not possible. This is because $phi(p_0^{a_0}p_1^{a_1}...p_r^{a_r})neq p_0^{a_0}p_1^{a_1}...p_r^{a_r}-1$.
Think about what the totient function entails: the number of integers less than the input that are coprime with it. Only with prime inputs is this one less than the input.
The totient function, however, does retain two properties, namely as reuns mentioned, that $phi(p^k)=p^k-p^{k-1}$ and $phi(n)phi(m)=phi(mn)$ when $m$ and $n$ are coprime. The proof of these is easily verifiable given a google search.
Thus, we can have a "direct" approach. Since powers of primes are always coprime to one another,
begin{align*}
phi(n)&=phi(p_0^{a_0}p_1^{a_1}...p_r^{a_r})\
&=phi(p_0^{a_0})phi(p_1^{a_1})...phi(p_r^{a_r})\
&=(p_0^{a_0}-p_0^{a_0-1})(p_1^{a_1}-p_1^{a_1-1})...(p_r^{a_r}-p_r^{a_r-1})\
&=p_0^{a_0}(1-1/p_0)p_1^{a_1}(1-1/p_1)...p_r^{a_r}(1-1/p_r)\
&=ndisplaystyleprod_{p|n}(1-1/p).
end{align*}
$endgroup$
add a comment |
$begingroup$
To be precise, your "kind" of derivation is not possible. This is because $phi(p_0^{a_0}p_1^{a_1}...p_r^{a_r})neq p_0^{a_0}p_1^{a_1}...p_r^{a_r}-1$.
Think about what the totient function entails: the number of integers less than the input that are coprime with it. Only with prime inputs is this one less than the input.
The totient function, however, does retain two properties, namely as reuns mentioned, that $phi(p^k)=p^k-p^{k-1}$ and $phi(n)phi(m)=phi(mn)$ when $m$ and $n$ are coprime. The proof of these is easily verifiable given a google search.
Thus, we can have a "direct" approach. Since powers of primes are always coprime to one another,
begin{align*}
phi(n)&=phi(p_0^{a_0}p_1^{a_1}...p_r^{a_r})\
&=phi(p_0^{a_0})phi(p_1^{a_1})...phi(p_r^{a_r})\
&=(p_0^{a_0}-p_0^{a_0-1})(p_1^{a_1}-p_1^{a_1-1})...(p_r^{a_r}-p_r^{a_r-1})\
&=p_0^{a_0}(1-1/p_0)p_1^{a_1}(1-1/p_1)...p_r^{a_r}(1-1/p_r)\
&=ndisplaystyleprod_{p|n}(1-1/p).
end{align*}
$endgroup$
add a comment |
$begingroup$
To be precise, your "kind" of derivation is not possible. This is because $phi(p_0^{a_0}p_1^{a_1}...p_r^{a_r})neq p_0^{a_0}p_1^{a_1}...p_r^{a_r}-1$.
Think about what the totient function entails: the number of integers less than the input that are coprime with it. Only with prime inputs is this one less than the input.
The totient function, however, does retain two properties, namely as reuns mentioned, that $phi(p^k)=p^k-p^{k-1}$ and $phi(n)phi(m)=phi(mn)$ when $m$ and $n$ are coprime. The proof of these is easily verifiable given a google search.
Thus, we can have a "direct" approach. Since powers of primes are always coprime to one another,
begin{align*}
phi(n)&=phi(p_0^{a_0}p_1^{a_1}...p_r^{a_r})\
&=phi(p_0^{a_0})phi(p_1^{a_1})...phi(p_r^{a_r})\
&=(p_0^{a_0}-p_0^{a_0-1})(p_1^{a_1}-p_1^{a_1-1})...(p_r^{a_r}-p_r^{a_r-1})\
&=p_0^{a_0}(1-1/p_0)p_1^{a_1}(1-1/p_1)...p_r^{a_r}(1-1/p_r)\
&=ndisplaystyleprod_{p|n}(1-1/p).
end{align*}
$endgroup$
To be precise, your "kind" of derivation is not possible. This is because $phi(p_0^{a_0}p_1^{a_1}...p_r^{a_r})neq p_0^{a_0}p_1^{a_1}...p_r^{a_r}-1$.
Think about what the totient function entails: the number of integers less than the input that are coprime with it. Only with prime inputs is this one less than the input.
The totient function, however, does retain two properties, namely as reuns mentioned, that $phi(p^k)=p^k-p^{k-1}$ and $phi(n)phi(m)=phi(mn)$ when $m$ and $n$ are coprime. The proof of these is easily verifiable given a google search.
Thus, we can have a "direct" approach. Since powers of primes are always coprime to one another,
begin{align*}
phi(n)&=phi(p_0^{a_0}p_1^{a_1}...p_r^{a_r})\
&=phi(p_0^{a_0})phi(p_1^{a_1})...phi(p_r^{a_r})\
&=(p_0^{a_0}-p_0^{a_0-1})(p_1^{a_1}-p_1^{a_1-1})...(p_r^{a_r}-p_r^{a_r-1})\
&=p_0^{a_0}(1-1/p_0)p_1^{a_1}(1-1/p_1)...p_r^{a_r}(1-1/p_r)\
&=ndisplaystyleprod_{p|n}(1-1/p).
end{align*}
answered Jan 15 at 20:50
Tejas RaoTejas Rao
16611
16611
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%2f3074184%2fdirect-passage-from-n-prime-to-n-non-prime-in-euler-totient-function-phi%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
$begingroup$
The two steps are $phi(p^k) = p^k-p^{k-1}$ and $phi(nm) = phi(n) phi(m)$ whenever $gcd(n,m)=1$ thus $phi(n) = prod_{p^k |n} phi(p^k) = nprod_{p^k |n} frac{phi(p^k) }{p^k}= n prod_{p| n} (1-p^{-1})$
$endgroup$
– reuns
Jan 15 at 8:19
1
$begingroup$
In particular, it is not true that $phi(p_0^{a_0}p_1^{a_1}cdots p_r^{a_r})=p_0^{a_0}p_1^{a_1}cdots p_r^{a_r}-1$ when $p_0^{a_0}p_1^{a_1}cdots p_r^{a_r}$ is not prime.
$endgroup$
– Greg Martin
Jan 15 at 8:28
$begingroup$
So such kind of derivation, as I suppose, it's not possible. Thanks
$endgroup$
– Alessar
Jan 15 at 8:31
$begingroup$
@reuns the symbol "$||$" means for "that divide"?
$endgroup$
– Alessar
Jan 15 at 9:13
1
$begingroup$
$p^k| n$ iff $p^k | n$ and $p^{k+1} nmid n$. In this setting $p$ means (ranging over) the primes and $p^k$ means over the prime powers
$endgroup$
– reuns
Jan 15 at 9:17