MathDB
Problems
Contests
National and Regional Contests
China Contests
China Team Selection Test
2023 China Team Selection Test
P4
2023 China TST Problem 4
2023 China TST Problem 4
Source: 2023 China TST Problem 4
March 14, 2023
number theory
China TST
Problem Statement
Given
m
,
n
∈
N
+
,
m,n\in\mathbb N_+,
m
,
n
∈
N
+
,
define
S
(
m
,
n
)
=
{
(
a
,
b
)
∈
N
+
2
∣
1
≤
a
≤
m
,
1
≤
b
≤
n
,
gcd
(
a
,
b
)
=
1
}
.
S(m,n)=\left\{(a,b)\in\mathbb N_+^2\mid 1\leq a\leq m,1\leq b\leq n,\gcd (a,b)=1\right\}.
S
(
m
,
n
)
=
{
(
a
,
b
)
∈
N
+
2
∣
1
≤
a
≤
m
,
1
≤
b
≤
n
,
g
cd
(
a
,
b
)
=
1
}
.
Prove that: for
∀
d
,
r
∈
N
+
,
\forall d,r\in\mathbb N_+,
∀
d
,
r
∈
N
+
,
there exists
m
,
n
∈
N
+
,
m
,
n
≥
d
m,n\in\mathbb N_+,m,n\geq d
m
,
n
∈
N
+
,
m
,
n
≥
d
and
∣
S
(
m
,
n
)
∣
≡
r
(
m
o
d
d
)
.
\left|S(m,n)\right|\equiv r\pmod d.
∣
S
(
m
,
n
)
∣
≡
r
(
mod
d
)
.
Back to Problems
View on AoPS