There a infinity numbers of $n$ such that $ phi (n) equiv 0 pmod{100} $
up vote
0
down vote
favorite
I have no clue what this part: $ phi (n) equiv 0 pmod {100} $ means.
$0 pmod {100}$ means I have an equivalence class $[0]$ in $mathbb{Z}$. This also means I have $100, 200, 300 ,cdots$ as the value of $ phi (n)$.
elementary-number-theory totient-function
add a comment |
up vote
0
down vote
favorite
I have no clue what this part: $ phi (n) equiv 0 pmod {100} $ means.
$0 pmod {100}$ means I have an equivalence class $[0]$ in $mathbb{Z}$. This also means I have $100, 200, 300 ,cdots$ as the value of $ phi (n)$.
elementary-number-theory totient-function
Well, it just means that you are to show that there are infinitely many natural numbers $n$ such that $100,|, varphi(n)$. For a hint note that $100=2^2times 5^2$ so, using the standard formulas for $varphi(n)$ try to build large families of good $n$.
– lulu
Nov 19 at 21:17
It just means it is divisible by 100. Hint: $101$ is prime
– Sorfosh
Nov 19 at 21:17
1
I think the toughest part of this question is to show that there exists at least one number $n$ such that $100| phi(n)$
– Doug M
Nov 19 at 21:25
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I have no clue what this part: $ phi (n) equiv 0 pmod {100} $ means.
$0 pmod {100}$ means I have an equivalence class $[0]$ in $mathbb{Z}$. This also means I have $100, 200, 300 ,cdots$ as the value of $ phi (n)$.
elementary-number-theory totient-function
I have no clue what this part: $ phi (n) equiv 0 pmod {100} $ means.
$0 pmod {100}$ means I have an equivalence class $[0]$ in $mathbb{Z}$. This also means I have $100, 200, 300 ,cdots$ as the value of $ phi (n)$.
elementary-number-theory totient-function
elementary-number-theory totient-function
edited Nov 19 at 22:29
Maged Saeed
547315
547315
asked Nov 19 at 21:12
thetha
268115
268115
Well, it just means that you are to show that there are infinitely many natural numbers $n$ such that $100,|, varphi(n)$. For a hint note that $100=2^2times 5^2$ so, using the standard formulas for $varphi(n)$ try to build large families of good $n$.
– lulu
Nov 19 at 21:17
It just means it is divisible by 100. Hint: $101$ is prime
– Sorfosh
Nov 19 at 21:17
1
I think the toughest part of this question is to show that there exists at least one number $n$ such that $100| phi(n)$
– Doug M
Nov 19 at 21:25
add a comment |
Well, it just means that you are to show that there are infinitely many natural numbers $n$ such that $100,|, varphi(n)$. For a hint note that $100=2^2times 5^2$ so, using the standard formulas for $varphi(n)$ try to build large families of good $n$.
– lulu
Nov 19 at 21:17
It just means it is divisible by 100. Hint: $101$ is prime
– Sorfosh
Nov 19 at 21:17
1
I think the toughest part of this question is to show that there exists at least one number $n$ such that $100| phi(n)$
– Doug M
Nov 19 at 21:25
Well, it just means that you are to show that there are infinitely many natural numbers $n$ such that $100,|, varphi(n)$. For a hint note that $100=2^2times 5^2$ so, using the standard formulas for $varphi(n)$ try to build large families of good $n$.
– lulu
Nov 19 at 21:17
Well, it just means that you are to show that there are infinitely many natural numbers $n$ such that $100,|, varphi(n)$. For a hint note that $100=2^2times 5^2$ so, using the standard formulas for $varphi(n)$ try to build large families of good $n$.
– lulu
Nov 19 at 21:17
It just means it is divisible by 100. Hint: $101$ is prime
– Sorfosh
Nov 19 at 21:17
It just means it is divisible by 100. Hint: $101$ is prime
– Sorfosh
Nov 19 at 21:17
1
1
I think the toughest part of this question is to show that there exists at least one number $n$ such that $100| phi(n)$
– Doug M
Nov 19 at 21:25
I think the toughest part of this question is to show that there exists at least one number $n$ such that $100| phi(n)$
– Doug M
Nov 19 at 21:25
add a comment |
3 Answers
3
active
oldest
votes
up vote
1
down vote
accepted
All natural numbers n have a decomposition into prime factors. (Fundamental theorem of Arithmetic)
$n = p_1^rp_2^scdots p_{i}^z$
$phi(n) = n (frac {p_1 -1}{p_1})(frac {p_2 -1}{p_2})cdots(frac {p_i -1}{p_i})$
If $100| phi(n)$
Then $5^3$ must be a factor of $n$
In fact $phi(5^3) = 4cdot 5^2 = 100$
There exists at least one $n$ such that $100|phi(n)$
For higher powers of $5,$ e.g. $phi(5^4) = 500$
And for factor the factor 2,
$phi(2cdot 5^3) = 2phi(5^3)cdot frac 12 = 100$
$forall jge 0, kge 3, phi(2^j5^k) equiv 0pmod {100}$
add a comment |
up vote
0
down vote
You may take this as a Hint:
Consider this sequence, does it have this property?
$1000,10000,100000,1000000,cdots$. Or equivalently, $10^k, k>2, kin mathbb{Z}.$ In fact, values of $phi(10^k)$ are multiples of $400$,
can you show Why?
add a comment |
up vote
0
down vote
Since $phi(ab)=phi(a)phi(b)$ for coprime $a,b$, it is sufficient to find some $a$ such that $phi(a)=100$ and then all numbers $n=ab$ give $phi(ab)equiv 0mod{100}$. Try $a=5^3$.
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
All natural numbers n have a decomposition into prime factors. (Fundamental theorem of Arithmetic)
$n = p_1^rp_2^scdots p_{i}^z$
$phi(n) = n (frac {p_1 -1}{p_1})(frac {p_2 -1}{p_2})cdots(frac {p_i -1}{p_i})$
If $100| phi(n)$
Then $5^3$ must be a factor of $n$
In fact $phi(5^3) = 4cdot 5^2 = 100$
There exists at least one $n$ such that $100|phi(n)$
For higher powers of $5,$ e.g. $phi(5^4) = 500$
And for factor the factor 2,
$phi(2cdot 5^3) = 2phi(5^3)cdot frac 12 = 100$
$forall jge 0, kge 3, phi(2^j5^k) equiv 0pmod {100}$
add a comment |
up vote
1
down vote
accepted
All natural numbers n have a decomposition into prime factors. (Fundamental theorem of Arithmetic)
$n = p_1^rp_2^scdots p_{i}^z$
$phi(n) = n (frac {p_1 -1}{p_1})(frac {p_2 -1}{p_2})cdots(frac {p_i -1}{p_i})$
If $100| phi(n)$
Then $5^3$ must be a factor of $n$
In fact $phi(5^3) = 4cdot 5^2 = 100$
There exists at least one $n$ such that $100|phi(n)$
For higher powers of $5,$ e.g. $phi(5^4) = 500$
And for factor the factor 2,
$phi(2cdot 5^3) = 2phi(5^3)cdot frac 12 = 100$
$forall jge 0, kge 3, phi(2^j5^k) equiv 0pmod {100}$
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
All natural numbers n have a decomposition into prime factors. (Fundamental theorem of Arithmetic)
$n = p_1^rp_2^scdots p_{i}^z$
$phi(n) = n (frac {p_1 -1}{p_1})(frac {p_2 -1}{p_2})cdots(frac {p_i -1}{p_i})$
If $100| phi(n)$
Then $5^3$ must be a factor of $n$
In fact $phi(5^3) = 4cdot 5^2 = 100$
There exists at least one $n$ such that $100|phi(n)$
For higher powers of $5,$ e.g. $phi(5^4) = 500$
And for factor the factor 2,
$phi(2cdot 5^3) = 2phi(5^3)cdot frac 12 = 100$
$forall jge 0, kge 3, phi(2^j5^k) equiv 0pmod {100}$
All natural numbers n have a decomposition into prime factors. (Fundamental theorem of Arithmetic)
$n = p_1^rp_2^scdots p_{i}^z$
$phi(n) = n (frac {p_1 -1}{p_1})(frac {p_2 -1}{p_2})cdots(frac {p_i -1}{p_i})$
If $100| phi(n)$
Then $5^3$ must be a factor of $n$
In fact $phi(5^3) = 4cdot 5^2 = 100$
There exists at least one $n$ such that $100|phi(n)$
For higher powers of $5,$ e.g. $phi(5^4) = 500$
And for factor the factor 2,
$phi(2cdot 5^3) = 2phi(5^3)cdot frac 12 = 100$
$forall jge 0, kge 3, phi(2^j5^k) equiv 0pmod {100}$
answered Nov 19 at 21:35
Doug M
43k31753
43k31753
add a comment |
add a comment |
up vote
0
down vote
You may take this as a Hint:
Consider this sequence, does it have this property?
$1000,10000,100000,1000000,cdots$. Or equivalently, $10^k, k>2, kin mathbb{Z}.$ In fact, values of $phi(10^k)$ are multiples of $400$,
can you show Why?
add a comment |
up vote
0
down vote
You may take this as a Hint:
Consider this sequence, does it have this property?
$1000,10000,100000,1000000,cdots$. Or equivalently, $10^k, k>2, kin mathbb{Z}.$ In fact, values of $phi(10^k)$ are multiples of $400$,
can you show Why?
add a comment |
up vote
0
down vote
up vote
0
down vote
You may take this as a Hint:
Consider this sequence, does it have this property?
$1000,10000,100000,1000000,cdots$. Or equivalently, $10^k, k>2, kin mathbb{Z}.$ In fact, values of $phi(10^k)$ are multiples of $400$,
can you show Why?
You may take this as a Hint:
Consider this sequence, does it have this property?
$1000,10000,100000,1000000,cdots$. Or equivalently, $10^k, k>2, kin mathbb{Z}.$ In fact, values of $phi(10^k)$ are multiples of $400$,
can you show Why?
answered Nov 19 at 21:26
Maged Saeed
547315
547315
add a comment |
add a comment |
up vote
0
down vote
Since $phi(ab)=phi(a)phi(b)$ for coprime $a,b$, it is sufficient to find some $a$ such that $phi(a)=100$ and then all numbers $n=ab$ give $phi(ab)equiv 0mod{100}$. Try $a=5^3$.
add a comment |
up vote
0
down vote
Since $phi(ab)=phi(a)phi(b)$ for coprime $a,b$, it is sufficient to find some $a$ such that $phi(a)=100$ and then all numbers $n=ab$ give $phi(ab)equiv 0mod{100}$. Try $a=5^3$.
add a comment |
up vote
0
down vote
up vote
0
down vote
Since $phi(ab)=phi(a)phi(b)$ for coprime $a,b$, it is sufficient to find some $a$ such that $phi(a)=100$ and then all numbers $n=ab$ give $phi(ab)equiv 0mod{100}$. Try $a=5^3$.
Since $phi(ab)=phi(a)phi(b)$ for coprime $a,b$, it is sufficient to find some $a$ such that $phi(a)=100$ and then all numbers $n=ab$ give $phi(ab)equiv 0mod{100}$. Try $a=5^3$.
answered Nov 19 at 21:36
Keith Backman
731148
731148
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%2f3005531%2fthere-a-infinity-numbers-of-n-such-that-phi-n-equiv-0-pmod100%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
Well, it just means that you are to show that there are infinitely many natural numbers $n$ such that $100,|, varphi(n)$. For a hint note that $100=2^2times 5^2$ so, using the standard formulas for $varphi(n)$ try to build large families of good $n$.
– lulu
Nov 19 at 21:17
It just means it is divisible by 100. Hint: $101$ is prime
– Sorfosh
Nov 19 at 21:17
1
I think the toughest part of this question is to show that there exists at least one number $n$ such that $100| phi(n)$
– Doug M
Nov 19 at 21:25