MathDB
Problems
Contests
National and Regional Contests
China Contests
China Northern MO
2015 China Northern MO
3
3
Part of
2015 China Northern MO
Problems
(1)
\phi (n)= 2^5 / 47 n , prime factorization
Source: China Northern MO 2015 grade 10 p3 CNMO
5/5/2024
If
n
=
p
1
a
1
,
p
2
a
2
.
.
.
p
s
a
s
n=p_1^{a_1},p_2^{a_2}...p_s^{a_s}
n
=
p
1
a
1
,
p
2
a
2
...
p
s
a
s
then
ϕ
(
n
)
=
n
(
1
−
1
p
1
)
(
1
−
1
p
2
)
.
.
.
(
1
−
1
p
s
)
\phi (n)=n \left(1- \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)...\left(1- \frac{1}{p_s}\right)
ϕ
(
n
)
=
n
(
1
−
p
1
1
)
(
1
−
p
2
1
)
...
(
1
−
p
s
1
)
. Find the smallest positive integer
n
n
n
such that
ϕ
(
n
)
=
2
5
47
n
.
\phi (n)=\frac{2^5}{47}n.
ϕ
(
n
)
=
47
2
5
n
.
number theory
prime factorization