MathDB
Problems
Contests
National and Regional Contests
Serbia Contests
Serbia National Math Olympiad
2022 Serbia National Math Olympiad
P4
P4
Part of
2022 Serbia National Math Olympiad
Problems
(1)
Number theory
Source: Serbian national olympiad 2022 P4
4/7/2022
Let
f
(
n
)
f(n)
f
(
n
)
be number of numbers
x
∈
{
1
,
2
,
⋯
,
n
}
x \in \{1,2,\cdots ,n\}
x
∈
{
1
,
2
,
⋯
,
n
}
,
n
∈
N
n\in\mathbb{N}
n
∈
N
, such that
g
c
d
(
x
,
n
)
gcd(x, n)
g
c
d
(
x
,
n
)
is either
1
1
1
or prime. Prove
∑
d
∣
n
f
(
d
)
+
φ
(
n
)
≥
2
n
\sum_{d|n} f(d) + \varphi(n) \geq 2n
d
∣
n
∑
f
(
d
)
+
φ
(
n
)
≥
2
n
For which
n
n
n
does equality hold?
number theory
phi function
Serbian competition
inequalities