Mixing
Prove that $varphi(n) = n cdot prodlimits_{i=1}^l frac{p_i - 1}{p_i}$
$begingroup$
In a course on cryptography we should prove that if $n$ is of the form $p_1^{k_1} cdot ldots cdot p_l^{k_l}$ and $p_1, ldots, p_l$ are all distinct prime numbers then $$
varphi left(prodlimits_{i=1}^{l} p_i^{k_i}right) = prodlimits_{i=1}^lp_i^{k_i-1} cdot (p_i - 1) = n cdot prodlimits_{i=1}^l frac{p_i - 1}{p_i}$$ holds.
We got the hint that if $n$ is a prime number, then $varphi(n) = n - 1$, but still I'm stuck on this. First of all, I'm not even sure how to interpret $prodlimits_{i=1}^lp_i^{k_i-1}$: As an example, take 330, which is composed of ${2, 3, 5, 11}$. Then $p_1 = 2, p_2 = 3, ldots$, but what is $p_1^{k_1}$ and $p_1^{k_1-1}$ in this context?
Next, I'm not sure how to prove this. Can someone give me a push in the right direction?
elementary-number-theory cryptography totient-function
edited Jan 10 at 15:45
amWhy
1
asked Jan 4 '14 at 18:31
Michael OslMichael Osl
1155
$endgroup$
|
show 3 more comments
$begingroup$
In a course on cryptography we should prove that if $n$ is of the form $p_1^{k_1} cdot ldots cdot p_l^{k_l}$ and $p_1, ldots, p_l$ are all distinct prime numbers then $$
varphi left(prodlimits_{i=1}^{l} p_i^{k_i}right) = prodlimits_{i=1}^lp_i^{k_i-1} cdot (p_i - 1) = n cdot prodlimits_{i=1}^l frac{p_i - 1}{p_i}$$ holds.
We got the hint that if $n$ is a prime number, then $varphi(n) = n - 1$, but still I'm stuck on this. First of all, I'm not even sure how to interpret $prodlimits_{i=1}^lp_i^{k_i-1}$: As an example, take 330, which is composed of ${2, 3, 5, 11}$. Then $p_1 = 2, p_2 = 3, ldots$, but what is $p_1^{k_1}$ and $p_1^{k_1-1}$ in this context?
Next, I'm not sure how to prove this. Can someone give me a push in the right direction?
elementary-number-theory cryptography totient-function
edited Jan 10 at 15:45
amWhy
1
asked Jan 4 '14 at 18:31
Michael OslMichael Osl
1155
$endgroup$
1
$begingroup$
You must prove that $varphi$ is a multiplicative function, i.e. if $gcd(a,b)=1$, then $varphi(ab)=varphi(a)varphi(b)$.
$endgroup$
– JPLF
Jan 4 '14 at 18:33
$begingroup$
In fact I have already proven that earlier on :) I'm still not sure what I should do with that, but I will think about it
$endgroup$
– Michael Osl
Jan 4 '14 at 18:37
1
$begingroup$
For your example, $330=2^1 3^1 5^1 11^1$, so $p_{1}^{k_1}=2^1$ and $p_1^{k_{1}-1}=2^0$.
$endgroup$
– user84413
Jan 4 '14 at 18:58
$begingroup$
@user84413 but isn't it always $p_i^0=1$ then?
$endgroup$
– Michael Osl
Jan 4 '14 at 19:05
1
$begingroup$
@ moeso What you're saying is correct if n is a square-free integer, such as 330; but they just mean in general that the primes $p_1,cdots,p_l$ are distinct; so for 360, for example, the primes 2, 3, and 5 are distinct.
$endgroup$
– user84413
Jan 4 '14 at 20:06
|
show 3 more comments
$begingroup$
In a course on cryptography we should prove that if $n$ is of the form $p_1^{k_1} cdot ldots cdot p_l^{k_l}$ and $p_1, ldots, p_l$ are all distinct prime numbers then $$
varphi left(prodlimits_{i=1}^{l} p_i^{k_i}right) = prodlimits_{i=1}^lp_i^{k_i-1} cdot (p_i - 1) = n cdot prodlimits_{i=1}^l frac{p_i - 1}{p_i}$$ holds.
We got the hint that if $n$ is a prime number, then $varphi(n) = n - 1$, but still I'm stuck on this. First of all, I'm not even sure how to interpret $prodlimits_{i=1}^lp_i^{k_i-1}$: As an example, take 330, which is composed of ${2, 3, 5, 11}$. Then $p_1 = 2, p_2 = 3, ldots$, but what is $p_1^{k_1}$ and $p_1^{k_1-1}$ in this context?
Next, I'm not sure how to prove this. Can someone give me a push in the right direction?
elementary-number-theory cryptography totient-function
edited Jan 10 at 15:45
amWhy
1
asked Jan 4 '14 at 18:31
Michael OslMichael Osl
1155
$endgroup$
In a course on cryptography we should prove that if $n$ is of the form $p_1^{k_1} cdot ldots cdot p_l^{k_l}$ and $p_1, ldots, p_l$ are all distinct prime numbers then $$
varphi left(prodlimits_{i=1}^{l} p_i^{k_i}right) = prodlimits_{i=1}^lp_i^{k_i-1} cdot (p_i - 1) = n cdot prodlimits_{i=1}^l frac{p_i - 1}{p_i}$$ holds.
We got the hint that if $n$ is a prime number, then $varphi(n) = n - 1$, but still I'm stuck on this. First of all, I'm not even sure how to interpret $prodlimits_{i=1}^lp_i^{k_i-1}$: As an example, take 330, which is composed of ${2, 3, 5, 11}$. Then $p_1 = 2, p_2 = 3, ldots$, but what is $p_1^{k_1}$ and $p_1^{k_1-1}$ in this context?
Next, I'm not sure how to prove this. Can someone give me a push in the right direction?
elementary-number-theory cryptography totient-function
elementary-number-theory cryptography totient-function
edited Jan 10 at 15:45
amWhy
1
asked Jan 4 '14 at 18:31
Michael OslMichael Osl
1155
edited Jan 10 at 15:45
amWhy
1
asked Jan 4 '14 at 18:31
Michael OslMichael Osl
1155
edited Jan 10 at 15:45
amWhy
1
edited Jan 10 at 15:45
amWhy
1
edited Jan 10 at 15:45
amWhy
1
1
asked Jan 4 '14 at 18:31
Michael OslMichael Osl
1155
asked Jan 4 '14 at 18:31
Michael OslMichael Osl
1155
asked Jan 4 '14 at 18:31
Michael OslMichael Osl
1155
1155
1
$begingroup$
You must prove that $varphi$ is a multiplicative function, i.e. if $gcd(a,b)=1$, then $varphi(ab)=varphi(a)varphi(b)$.
$endgroup$
– JPLF
Jan 4 '14 at 18:33
$begingroup$
In fact I have already proven that earlier on :) I'm still not sure what I should do with that, but I will think about it
$endgroup$
– Michael Osl
Jan 4 '14 at 18:37
1
$begingroup$
For your example, $330=2^1 3^1 5^1 11^1$, so $p_{1}^{k_1}=2^1$ and $p_1^{k_{1}-1}=2^0$.
$endgroup$
– user84413
Jan 4 '14 at 18:58
$begingroup$
@user84413 but isn't it always $p_i^0=1$ then?
$endgroup$
– Michael Osl
Jan 4 '14 at 19:05
1
$begingroup$
@ moeso What you're saying is correct if n is a square-free integer, such as 330; but they just mean in general that the primes $p_1,cdots,p_l$ are distinct; so for 360, for example, the primes 2, 3, and 5 are distinct.
$endgroup$
– user84413
Jan 4 '14 at 20:06
|
show 3 more comments
1
$begingroup$
You must prove that $varphi$ is a multiplicative function, i.e. if $gcd(a,b)=1$, then $varphi(ab)=varphi(a)varphi(b)$.
$endgroup$
– JPLF
Jan 4 '14 at 18:33
$begingroup$
In fact I have already proven that earlier on :) I'm still not sure what I should do with that, but I will think about it
$endgroup$
– Michael Osl
Jan 4 '14 at 18:37
1
$begingroup$
For your example, $330=2^1 3^1 5^1 11^1$, so $p_{1}^{k_1}=2^1$ and $p_1^{k_{1}-1}=2^0$.
$endgroup$
– user84413
Jan 4 '14 at 18:58
$begingroup$
@user84413 but isn't it always $p_i^0=1$ then?
$endgroup$
– Michael Osl
Jan 4 '14 at 19:05
1
$begingroup$
@ moeso What you're saying is correct if n is a square-free integer, such as 330; but they just mean in general that the primes $p_1,cdots,p_l$ are distinct; so for 360, for example, the primes 2, 3, and 5 are distinct.
$endgroup$
– user84413
Jan 4 '14 at 20:06
1
1
$begingroup$
You must prove that $varphi$ is a multiplicative function, i.e. if $gcd(a,b)=1$, then $varphi(ab)=varphi(a)varphi(b)$.
$endgroup$
– JPLF
Jan 4 '14 at 18:33
$begingroup$
You must prove that $varphi$ is a multiplicative function, i.e. if $gcd(a,b)=1$, then $varphi(ab)=varphi(a)varphi(b)$.
$endgroup$
– JPLF
Jan 4 '14 at 18:33
$begingroup$
In fact I have already proven that earlier on :) I'm still not sure what I should do with that, but I will think about it
$endgroup$
– Michael Osl
Jan 4 '14 at 18:37
$begingroup$
In fact I have already proven that earlier on :) I'm still not sure what I should do with that, but I will think about it
$endgroup$
– Michael Osl
Jan 4 '14 at 18:37
1
1
$begingroup$
For your example, $330=2^1 3^1 5^1 11^1$, so $p_{1}^{k_1}=2^1$ and $p_1^{k_{1}-1}=2^0$.
$endgroup$
– user84413
Jan 4 '14 at 18:58
$begingroup$
For your example, $330=2^1 3^1 5^1 11^1$, so $p_{1}^{k_1}=2^1$ and $p_1^{k_{1}-1}=2^0$.
$endgroup$
– user84413
Jan 4 '14 at 18:58
$begingroup$
@user84413 but isn't it always $p_i^0=1$ then?
$endgroup$
– Michael Osl
Jan 4 '14 at 19:05
$begingroup$
@user84413 but isn't it always $p_i^0=1$ then?
$endgroup$
– Michael Osl
Jan 4 '14 at 19:05
1
1
$begingroup$
@ moeso What you're saying is correct if n is a square-free integer, such as 330; but they just mean in general that the primes $p_1,cdots,p_l$ are distinct; so for 360, for example, the primes 2, 3, and 5 are distinct.
$endgroup$
– user84413
Jan 4 '14 at 20:06
$begingroup$
@ moeso What you're saying is correct if n is a square-free integer, such as 330; but they just mean in general that the primes $p_1,cdots,p_l$ are distinct; so for 360, for example, the primes 2, 3, and 5 are distinct.
$endgroup$
– user84413
Jan 4 '14 at 20:06
|
show 3 more comments
2 Answers
2
active
oldest
votes
$begingroup$
It's straightforward to see that for a prime number $p$ and a natural number $n$, we have $varphi(p^n)=p^n{p-1over p}$. You said you already know the following property: if $gcd(a,b)=1$, then $varphi(ab)=varphi(a)varphi(b)$. It can be extended for any finite product of coprime natural numbers. So, suppose $n$ is a natural number. By the unique factorization theorem, there exist prime numbers $p_1,dots,p_l$ and natural numbers $k_1,dots,k_l$ such that
$$n = p_1^{k_1}p_2^{k_2}dots p_l^{k_l}.$$
The factors $p_1^{k_1},dots,p_l^{k_l}$ are all relatively prime. So
$$varphi(n) = varphi(p_1^{k_1}p_2^{k_2}dots p_l^{k_l})= varphi(p_1^{k_1})varphi(p_2^{k_2})dotsvarphi(p_l^{k_l}) = p_1^{k_1}{p_1-1over p_1}p_2^{k_2}{p_2 -1over p_2}dots p_l^{k_l}{p_l-1over p_l}.$$
The last term is easily seen to be equal to $displaystyle n prod_{i=1}^l {p_i-1over p_i}$, the result we were seeking.
answered Jan 4 '14 at 18:46
JPLFJPLF
56029
$endgroup$
add a comment |
$begingroup$
Let $1<n = p_1^{k_1}p_2^{k_2}dots p_l^{k_l}$ be the canonical decomposition of to prime numbers. We prove by induction on $l$, the distinct numbers of primes, that
$$(1) phi(prodlimits_{i=1}^{l} p_i^{k_i}) = n cdot prodlimits_{i=1}^l(p_i - 1) / p_i$$
For $l=1$: It is clear from the fact that $phi$ multiplicative function if $gcd(a,b)=1$, then $phi(ab)=phi(a)phi(b)$.
Suppose that $(1)$ is true for $l=i$.
$$gcd(p_1^{k_1},p_2^{k_2},dots ,p_i^{k_i},p_{i+1}^{k_{i+1}})=1$$
Using again the fact that $phi$ multiplicative function, we will have:
$$ (2) phi((p_1^{k_1}p_2^{k_2}dots p_i^{k_i})p_{i+1}^{k_{i+1}})=phi(p_1^{k_1}p_2^{k_2}dots p_i^{k_i})phi(p_{i+1}^{k_{i+1}}) $$
But, we know that if $p$ is a prime number and $s>0$, then
$$phi(p^s)=p^s-p^{s-1}$$
Therefore, $(2)$ becomes to be
$$(3) phi(p_1^{k_1}p_2^{k_2}dots p_i^{k_i})(p_{i+1}^{k_{i+1}}-p_{i+1}^{k_{i+1}-1})$$
And now, by the induction hypothesis, we can substitute:
$$phi(p_1^{k_1}p_2^{k_2}dots p_i^{k_i})=(p_1^{k_1}-p_1^{k_1-1})(p_2^{k_2}-p_2^{k_2-1})cdots (p_i^{k_i}-p_i^{k_i-1})$$
into $(3)$, to get
$$ phi(p_1^{k_1}p_2^{k_2}dots p_i^{k_i}p_{i+1}^{k_{i+1}})=(p_1^{k_1}-p_1^{k_1-1})(p_2^{k_2}-p_2^{k_2-1})cdots (p_i^{k_i}-p_i^{k_i-1})(p_{i+1}^{k_{i+1}}-p_{i+1}^{k_{i+1}-1}) $$
And we are done.
Notice that you can factor out $p_1^{k_1}p_2^{k_2}dots p_{i+1}^{k_{i+1}}$.
answered Jan 4 '14 at 19:35
Salech AlhasovSalech Alhasov
4,84712037
$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%2f627213%2fprove-that-varphin-n-cdot-prod-limits-i-1l-fracp-i-1p-i%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$
It's straightforward to see that for a prime number $p$ and a natural number $n$, we have $varphi(p^n)=p^n{p-1over p}$. You said you already know the following property: if $gcd(a,b)=1$, then $varphi(ab)=varphi(a)varphi(b)$. It can be extended for any finite product of coprime natural numbers. So, suppose $n$ is a natural number. By the unique factorization theorem, there exist prime numbers $p_1,dots,p_l$ and natural numbers $k_1,dots,k_l$ such that
$$n = p_1^{k_1}p_2^{k_2}dots p_l^{k_l}.$$
The factors $p_1^{k_1},dots,p_l^{k_l}$ are all relatively prime. So
$$varphi(n) = varphi(p_1^{k_1}p_2^{k_2}dots p_l^{k_l})= varphi(p_1^{k_1})varphi(p_2^{k_2})dotsvarphi(p_l^{k_l}) = p_1^{k_1}{p_1-1over p_1}p_2^{k_2}{p_2 -1over p_2}dots p_l^{k_l}{p_l-1over p_l}.$$
The last term is easily seen to be equal to $displaystyle n prod_{i=1}^l {p_i-1over p_i}$, the result we were seeking.
answered Jan 4 '14 at 18:46
JPLFJPLF
56029
$endgroup$
add a comment |
$begingroup$
It's straightforward to see that for a prime number $p$ and a natural number $n$, we have $varphi(p^n)=p^n{p-1over p}$. You said you already know the following property: if $gcd(a,b)=1$, then $varphi(ab)=varphi(a)varphi(b)$. It can be extended for any finite product of coprime natural numbers. So, suppose $n$ is a natural number. By the unique factorization theorem, there exist prime numbers $p_1,dots,p_l$ and natural numbers $k_1,dots,k_l$ such that
$$n = p_1^{k_1}p_2^{k_2}dots p_l^{k_l}.$$
The factors $p_1^{k_1},dots,p_l^{k_l}$ are all relatively prime. So
$$varphi(n) = varphi(p_1^{k_1}p_2^{k_2}dots p_l^{k_l})= varphi(p_1^{k_1})varphi(p_2^{k_2})dotsvarphi(p_l^{k_l}) = p_1^{k_1}{p_1-1over p_1}p_2^{k_2}{p_2 -1over p_2}dots p_l^{k_l}{p_l-1over p_l}.$$
The last term is easily seen to be equal to $displaystyle n prod_{i=1}^l {p_i-1over p_i}$, the result we were seeking.
answered Jan 4 '14 at 18:46
JPLFJPLF
56029
$endgroup$
add a comment |
$begingroup$
It's straightforward to see that for a prime number $p$ and a natural number $n$, we have $varphi(p^n)=p^n{p-1over p}$. You said you already know the following property: if $gcd(a,b)=1$, then $varphi(ab)=varphi(a)varphi(b)$. It can be extended for any finite product of coprime natural numbers. So, suppose $n$ is a natural number. By the unique factorization theorem, there exist prime numbers $p_1,dots,p_l$ and natural numbers $k_1,dots,k_l$ such that
$$n = p_1^{k_1}p_2^{k_2}dots p_l^{k_l}.$$
The factors $p_1^{k_1},dots,p_l^{k_l}$ are all relatively prime. So
$$varphi(n) = varphi(p_1^{k_1}p_2^{k_2}dots p_l^{k_l})= varphi(p_1^{k_1})varphi(p_2^{k_2})dotsvarphi(p_l^{k_l}) = p_1^{k_1}{p_1-1over p_1}p_2^{k_2}{p_2 -1over p_2}dots p_l^{k_l}{p_l-1over p_l}.$$
The last term is easily seen to be equal to $displaystyle n prod_{i=1}^l {p_i-1over p_i}$, the result we were seeking.
answered Jan 4 '14 at 18:46
JPLFJPLF
56029
$endgroup$
It's straightforward to see that for a prime number $p$ and a natural number $n$, we have $varphi(p^n)=p^n{p-1over p}$. You said you already know the following property: if $gcd(a,b)=1$, then $varphi(ab)=varphi(a)varphi(b)$. It can be extended for any finite product of coprime natural numbers. So, suppose $n$ is a natural number. By the unique factorization theorem, there exist prime numbers $p_1,dots,p_l$ and natural numbers $k_1,dots,k_l$ such that
$$n = p_1^{k_1}p_2^{k_2}dots p_l^{k_l}.$$
The factors $p_1^{k_1},dots,p_l^{k_l}$ are all relatively prime. So
$$varphi(n) = varphi(p_1^{k_1}p_2^{k_2}dots p_l^{k_l})= varphi(p_1^{k_1})varphi(p_2^{k_2})dotsvarphi(p_l^{k_l}) = p_1^{k_1}{p_1-1over p_1}p_2^{k_2}{p_2 -1over p_2}dots p_l^{k_l}{p_l-1over p_l}.$$
The last term is easily seen to be equal to $displaystyle n prod_{i=1}^l {p_i-1over p_i}$, the result we were seeking.
answered Jan 4 '14 at 18:46
JPLFJPLF
56029
answered Jan 4 '14 at 18:46
JPLFJPLF
56029
answered Jan 4 '14 at 18:46
JPLFJPLF
56029
answered Jan 4 '14 at 18:46
JPLFJPLF
56029
56029
add a comment |
add a comment |
$begingroup$
Let $1<n = p_1^{k_1}p_2^{k_2}dots p_l^{k_l}$ be the canonical decomposition of to prime numbers. We prove by induction on $l$, the distinct numbers of primes, that
$$(1) phi(prodlimits_{i=1}^{l} p_i^{k_i}) = n cdot prodlimits_{i=1}^l(p_i - 1) / p_i$$
For $l=1$: It is clear from the fact that $phi$ multiplicative function if $gcd(a,b)=1$, then $phi(ab)=phi(a)phi(b)$.
Suppose that $(1)$ is true for $l=i$.
$$gcd(p_1^{k_1},p_2^{k_2},dots ,p_i^{k_i},p_{i+1}^{k_{i+1}})=1$$
Using again the fact that $phi$ multiplicative function, we will have:
$$ (2) phi((p_1^{k_1}p_2^{k_2}dots p_i^{k_i})p_{i+1}^{k_{i+1}})=phi(p_1^{k_1}p_2^{k_2}dots p_i^{k_i})phi(p_{i+1}^{k_{i+1}}) $$
But, we know that if $p$ is a prime number and $s>0$, then
$$phi(p^s)=p^s-p^{s-1}$$
Therefore, $(2)$ becomes to be
$$(3) phi(p_1^{k_1}p_2^{k_2}dots p_i^{k_i})(p_{i+1}^{k_{i+1}}-p_{i+1}^{k_{i+1}-1})$$
And now, by the induction hypothesis, we can substitute:
$$phi(p_1^{k_1}p_2^{k_2}dots p_i^{k_i})=(p_1^{k_1}-p_1^{k_1-1})(p_2^{k_2}-p_2^{k_2-1})cdots (p_i^{k_i}-p_i^{k_i-1})$$
into $(3)$, to get
$$ phi(p_1^{k_1}p_2^{k_2}dots p_i^{k_i}p_{i+1}^{k_{i+1}})=(p_1^{k_1}-p_1^{k_1-1})(p_2^{k_2}-p_2^{k_2-1})cdots (p_i^{k_i}-p_i^{k_i-1})(p_{i+1}^{k_{i+1}}-p_{i+1}^{k_{i+1}-1}) $$
And we are done.
Notice that you can factor out $p_1^{k_1}p_2^{k_2}dots p_{i+1}^{k_{i+1}}$.
answered Jan 4 '14 at 19:35
Salech AlhasovSalech Alhasov
4,84712037
$endgroup$
add a comment |
$begingroup$
Let $1<n = p_1^{k_1}p_2^{k_2}dots p_l^{k_l}$ be the canonical decomposition of to prime numbers. We prove by induction on $l$, the distinct numbers of primes, that
$$(1) phi(prodlimits_{i=1}^{l} p_i^{k_i}) = n cdot prodlimits_{i=1}^l(p_i - 1) / p_i$$
For $l=1$: It is clear from the fact that $phi$ multiplicative function if $gcd(a,b)=1$, then $phi(ab)=phi(a)phi(b)$.
Suppose that $(1)$ is true for $l=i$.
$$gcd(p_1^{k_1},p_2^{k_2},dots ,p_i^{k_i},p_{i+1}^{k_{i+1}})=1$$
Using again the fact that $phi$ multiplicative function, we will have:
$$ (2) phi((p_1^{k_1}p_2^{k_2}dots p_i^{k_i})p_{i+1}^{k_{i+1}})=phi(p_1^{k_1}p_2^{k_2}dots p_i^{k_i})phi(p_{i+1}^{k_{i+1}}) $$
But, we know that if $p$ is a prime number and $s>0$, then
$$phi(p^s)=p^s-p^{s-1}$$
Therefore, $(2)$ becomes to be
$$(3) phi(p_1^{k_1}p_2^{k_2}dots p_i^{k_i})(p_{i+1}^{k_{i+1}}-p_{i+1}^{k_{i+1}-1})$$
And now, by the induction hypothesis, we can substitute:
$$phi(p_1^{k_1}p_2^{k_2}dots p_i^{k_i})=(p_1^{k_1}-p_1^{k_1-1})(p_2^{k_2}-p_2^{k_2-1})cdots (p_i^{k_i}-p_i^{k_i-1})$$
into $(3)$, to get
$$ phi(p_1^{k_1}p_2^{k_2}dots p_i^{k_i}p_{i+1}^{k_{i+1}})=(p_1^{k_1}-p_1^{k_1-1})(p_2^{k_2}-p_2^{k_2-1})cdots (p_i^{k_i}-p_i^{k_i-1})(p_{i+1}^{k_{i+1}}-p_{i+1}^{k_{i+1}-1}) $$
And we are done.
Notice that you can factor out $p_1^{k_1}p_2^{k_2}dots p_{i+1}^{k_{i+1}}$.
answered Jan 4 '14 at 19:35
Salech AlhasovSalech Alhasov
4,84712037
$endgroup$
add a comment |
$begingroup$
Let $1<n = p_1^{k_1}p_2^{k_2}dots p_l^{k_l}$ be the canonical decomposition of to prime numbers. We prove by induction on $l$, the distinct numbers of primes, that
$$(1) phi(prodlimits_{i=1}^{l} p_i^{k_i}) = n cdot prodlimits_{i=1}^l(p_i - 1) / p_i$$
For $l=1$: It is clear from the fact that $phi$ multiplicative function if $gcd(a,b)=1$, then $phi(ab)=phi(a)phi(b)$.
Suppose that $(1)$ is true for $l=i$.
$$gcd(p_1^{k_1},p_2^{k_2},dots ,p_i^{k_i},p_{i+1}^{k_{i+1}})=1$$
Using again the fact that $phi$ multiplicative function, we will have:
$$ (2) phi((p_1^{k_1}p_2^{k_2}dots p_i^{k_i})p_{i+1}^{k_{i+1}})=phi(p_1^{k_1}p_2^{k_2}dots p_i^{k_i})phi(p_{i+1}^{k_{i+1}}) $$
But, we know that if $p$ is a prime number and $s>0$, then
$$phi(p^s)=p^s-p^{s-1}$$
Therefore, $(2)$ becomes to be
$$(3) phi(p_1^{k_1}p_2^{k_2}dots p_i^{k_i})(p_{i+1}^{k_{i+1}}-p_{i+1}^{k_{i+1}-1})$$
And now, by the induction hypothesis, we can substitute:
$$phi(p_1^{k_1}p_2^{k_2}dots p_i^{k_i})=(p_1^{k_1}-p_1^{k_1-1})(p_2^{k_2}-p_2^{k_2-1})cdots (p_i^{k_i}-p_i^{k_i-1})$$
into $(3)$, to get
$$ phi(p_1^{k_1}p_2^{k_2}dots p_i^{k_i}p_{i+1}^{k_{i+1}})=(p_1^{k_1}-p_1^{k_1-1})(p_2^{k_2}-p_2^{k_2-1})cdots (p_i^{k_i}-p_i^{k_i-1})(p_{i+1}^{k_{i+1}}-p_{i+1}^{k_{i+1}-1}) $$
And we are done.
Notice that you can factor out $p_1^{k_1}p_2^{k_2}dots p_{i+1}^{k_{i+1}}$.
answered Jan 4 '14 at 19:35
Salech AlhasovSalech Alhasov
4,84712037
$endgroup$
Let $1<n = p_1^{k_1}p_2^{k_2}dots p_l^{k_l}$ be the canonical decomposition of to prime numbers. We prove by induction on $l$, the distinct numbers of primes, that
$$(1) phi(prodlimits_{i=1}^{l} p_i^{k_i}) = n cdot prodlimits_{i=1}^l(p_i - 1) / p_i$$
For $l=1$: It is clear from the fact that $phi$ multiplicative function if $gcd(a,b)=1$, then $phi(ab)=phi(a)phi(b)$.
Suppose that $(1)$ is true for $l=i$.
$$gcd(p_1^{k_1},p_2^{k_2},dots ,p_i^{k_i},p_{i+1}^{k_{i+1}})=1$$
Using again the fact that $phi$ multiplicative function, we will have:
$$ (2) phi((p_1^{k_1}p_2^{k_2}dots p_i^{k_i})p_{i+1}^{k_{i+1}})=phi(p_1^{k_1}p_2^{k_2}dots p_i^{k_i})phi(p_{i+1}^{k_{i+1}}) $$
But, we know that if $p$ is a prime number and $s>0$, then
$$phi(p^s)=p^s-p^{s-1}$$
Therefore, $(2)$ becomes to be
$$(3) phi(p_1^{k_1}p_2^{k_2}dots p_i^{k_i})(p_{i+1}^{k_{i+1}}-p_{i+1}^{k_{i+1}-1})$$
And now, by the induction hypothesis, we can substitute:
$$phi(p_1^{k_1}p_2^{k_2}dots p_i^{k_i})=(p_1^{k_1}-p_1^{k_1-1})(p_2^{k_2}-p_2^{k_2-1})cdots (p_i^{k_i}-p_i^{k_i-1})$$
into $(3)$, to get
$$ phi(p_1^{k_1}p_2^{k_2}dots p_i^{k_i}p_{i+1}^{k_{i+1}})=(p_1^{k_1}-p_1^{k_1-1})(p_2^{k_2}-p_2^{k_2-1})cdots (p_i^{k_i}-p_i^{k_i-1})(p_{i+1}^{k_{i+1}}-p_{i+1}^{k_{i+1}-1}) $$
And we are done.
Notice that you can factor out $p_1^{k_1}p_2^{k_2}dots p_{i+1}^{k_{i+1}}$.
answered Jan 4 '14 at 19:35
Salech AlhasovSalech Alhasov
4,84712037
answered Jan 4 '14 at 19:35
Salech AlhasovSalech Alhasov
4,84712037
answered Jan 4 '14 at 19:35
Salech AlhasovSalech Alhasov
4,84712037
answered Jan 4 '14 at 19:35
Salech AlhasovSalech Alhasov
4,84712037
4,84712037
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%2f627213%2fprove-that-varphin-n-cdot-prod-limits-i-1l-fracp-i-1p-i%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
1
$begingroup$
You must prove that $varphi$ is a multiplicative function, i.e. if $gcd(a,b)=1$, then $varphi(ab)=varphi(a)varphi(b)$.
$endgroup$
– JPLF
Jan 4 '14 at 18:33
$begingroup$
In fact I have already proven that earlier on :) I'm still not sure what I should do with that, but I will think about it
$endgroup$
– Michael Osl
Jan 4 '14 at 18:37
1
$begingroup$
For your example, $330=2^1 3^1 5^1 11^1$, so $p_{1}^{k_1}=2^1$ and $p_1^{k_{1}-1}=2^0$.
$endgroup$
– user84413
Jan 4 '14 at 18:58
$begingroup$
@user84413 but isn't it always $p_i^0=1$ then?
$endgroup$
– Michael Osl
Jan 4 '14 at 19:05
1
$begingroup$
@ moeso What you're saying is correct if n is a square-free integer, such as 330; but they just mean in general that the primes $p_1,cdots,p_l$ are distinct; so for 360, for example, the primes 2, 3, and 5 are distinct.
$endgroup$
– user84413
Jan 4 '14 at 20:06