线性不定方程

Full Solutions

专题: General / 综合
难度: L2
来源: QuantQuestion

个人笔记

题目详情

求所有整数解 $(x,y)$ 使得 $3x+7y=10000$ 。

所有解可写为 $x=a+7n$ 、 $y=b-3n$ （ $n$ 为任意整数），其中 $b$ 为最小正整数。求 $ab$ 。

英文原题

Find all pairs of integers $(x,y)$ such that $3x + 7y = 10000$ . All of the solutions can be written in the form $x = a + 7n$ and $y = b - 3n$ , where $n$ is any arbitrary integer and $a,b$ are integers such that $b$ is a minimal positive integer. Find $ab$ .

解析

利用 $3(-2)+7(1)=1$ ，乘以 10000 得一个解 $(-20000,10000)$ 。

通解为

(x,y)=(-20000+7n,\ 10000-3n).

令 $m=n-3333$ ，可改写为

(x,y)=(3331+7m,\ 1-3m),

此时 $b=1$ 最小正，故 $ab=3331$ 。

英文解析

Since $3$ and $7$ are clearly relatively prime, there must exist a solution to this equation. We note that $3(-2) + 7(1) = 1$ , so if we multiply by $10000$ on both sides, $3(-20000) + 7(10000) = 10000$ , which means $(x,y) = (-20000,10000)$ is a solution to this equation. By the latter hint, we can write all solutions to this equation in the form
$(-20000 + 7n, 10000 - 3n)$ .

We now need to reduce this equation so that the integer in front of $-3n$ is as small as possible. We note that $9999 = 3 \cdot 3333$ , so we note that if $m = n - 3333$ , we can rewrite the form of solutions as
$(-20000 + 7(m + 3333), 10000 - 3(m + 3333)) = (3331 + 7m, 1 - 3m)$ .

This is the general form where $b$ is as small as possible but possible. In particular $ab = 3331$ .