MathDB
Problems
Contests
National and Regional Contests
China Contests
China Team Selection Test
2024 China Team Selection Test
3
3
Part of
2024 China Team Selection Test
Problems
(1)
Nightmare NT comes again
Source: 2024 Chinese TST P3
3/6/2024
Given positive integer
M
.
M.
M
.
For any
n
∈
N
+
,
n\in\mathbb N_+,
n
∈
N
+
,
let
h
(
n
)
h(n)
h
(
n
)
be the number of elements in
[
n
]
[n]
[
n
]
that are coprime to
M
.
M.
M
.
Define
β
:
=
h
(
M
)
M
.
\beta :=\frac {h(M)}M.
β
:=
M
h
(
M
)
.
Proof: there are at least
M
3
\frac M3
3
M
elements
n
n
n
in
[
M
]
,
[M],
[
M
]
,
satisfy
∣
h
(
n
)
−
β
n
∣
≤
β
⋅
2
ω
(
M
)
−
3
+
1.
\left| h(n)-\beta n\right|\le\sqrt{\beta\cdot 2^{\omega(M)-3}}+1.
∣
h
(
n
)
−
β
n
∣
≤
β
⋅
2
ω
(
M
)
−
3
+
1.
Here
[
n
]
:
=
{
1
,
2
,
…
,
n
}
[n]:=\{1,2,\ldots ,n\}
[
n
]
:=
{
1
,
2
,
…
,
n
}
for all positive integer
n
.
n.
n
.
Proposed by Bin Wang
number theory
2024 CTST