MathDB
Problems
Contests
National and Regional Contests
China Contests
China Team Selection Test
2023 China Team Selection Test
P4
P4
Part of
2023 China Team Selection Test
Problems
(1)
2023 China TST Problem 4
Source: 2023 China TST Problem 4
3/14/2023
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
)
.
number theory
China TST