丢番图方程-因式分解

保理是一个非常强大的解决工具吗丢番图方程．有时因式分解可以使丢番图方程豁然洞开。我们不讨论它有多好，有多强大，我们来演示一下因式分解是如何帮助解丢番图方程的。我们从二次方程开始，我们已经知道如何分解二次方程了。

这只是一种奇特的方法考虑一个特定数的因数来求方程的整数解。

整数解是什么 $(x, y)$这个方程 $(x + 2) (y-3) = 6 ?$

---

现在我们知道了 $x$和 $y$都是整数。所以 $(x + 2)$和 $(y-3)$一定是整数吗 $6$，即这两个因素必须是其中之一 $(1,6),(6, 1),(2),(2、3),(1,6),(6,1),(2)$或 $(2、3)$．这意味着我们有以下8个可能的线性方程组:

$\{对齐}开始x + 2 & = 1 & y-3& = 6 & \ qquad (1) \ \ x + 2 & = 6 & y-3& = 1 & \ qquad (2) \ \ x + 2 & = 3, & y-3& = 2 & \ qquad (3) \ \ x + 2 & = 2 & y-3 & = 3 & \ qquad (4) \ \ x + 2 & = 1 & y-3& = 6 & \ qquad (5) \ \ x + 2 & = 6 & y-3& = 1 & \ qquad (6) \ \ x + 2 & = 3, & y-3& = 2 & \ qquad (7) \ \ x + 2 & = 2 & y-3 & = 3。& \ qquad结束(8)\{对齐}$

因此，有序整数对 $(x, y)$满足给定方程的是

$(9),(4, 4),(1、5),(0,6),(3),(8,2),(5、1),(4 0)\ _ \广场$

这是一个非常强大的工具，有时可以解决看似不可能的问题。

有多少正整数 $x$是不是两者都有 $x$和 $x + 99$完全平方数吗?

---

这个问题不需要解决方案，只需要解决方案的数量。但是，为了解释，我会找到它们。

让我们从最明显的开始:让 $x = r ^ 2$和 $x + 99 = m ^ 2$,然后 $R²+99 = m²$．减去 $r ^ 2$等式两边都有结果

$\{对齐}开始m ^ 2 - r ^ 2 & = 99 \ \ (m + r)(先生)& = 99。结束\{对齐}$

正如我们之前所做的，我们将考虑因素 $99$,这是 $11(99),(9日)$和 $(33)$．换句话说，我们有以下六对线性方程:

$\{对齐}开始m + " = 1 & m-r& = 99 & \ qquad (1) \ \ m + " = 99 & m-r& = 1 & \ qquad (2) \ \ m + " = 9, & m-r& = 11 & \ qquad (3) \ \ m + " = 11日& m-r& = 9 & \ qquad (4) \ \ m + " = 3, & m-r& = 33 & \ qquad (5) \ \ m + " = 33 & m-r& = 3。& \ qquad结束(6)\{对齐}$

这些线性方程组的解分别为

$猴\开始{对齐}= 50,& " = -49 & \ qquad(1)“猴\ \ = 50,& " = 49 & \ qquad(2)“猴\ \ = 10,& " = 1 & \ qquad(3)“猴\ \ = 10,& " = 1 & \ qquad(4)“猴\ \ = 18日& " = -15 & \ qquad(5) ' & "猴\ \ = 18日= 15。& \ qquad(6)“\{对齐}$

然后自 $x = r ^ 2$，有三个这样的 $x$满足条件:

$\{对齐}开始(1)^ 2 = 1 ^ 2 & = 1 \ \(-15)^ 2 = 15 ^ 2 & = 225 \ \(-49)^ 2 = 49 ^ 2 & = 2401。\ \ _ \广场结束{对齐}$

注意:相应的 $m ^ 2 = r ^ 2 + 99$是

$开始\{对齐}1 + 99 = 100 & = 10 ^ 2 \ \ 225 + 99 = 324 & = 18 ^ 2 \ \ 2401 + 99 = 2500 & = 50 ^ 2。结束\{对齐}$

西蒙最喜欢的因式分解技巧(SFFT),也称为完成矩形，是对形式表达式的简单而巧妙的因式分解 $xy + xn + ym +锰、$在哪里 $x$和 $y$是变量(通常是整型变量)，和 $米$和 $n$都是整数。

注意，这个可以被分解为

$xy + xn + ym + mn = x (y + n) + m (y + n) = (x + m) (y + n)。$

两种特殊情况(也是非常常见的)是when $(m, n) = (1,1)$和 $(m, n) = (1,1)$．也就是说,

$xy + x + y + 1 = (x + 1) (y + 1), \四xy-x-y + 1 = (x - 1) (y-1)。$

虽然这是一个基本且容易记住的事实，但在解丢番图方程时，这种方法通常很有用。

求方程的所有积分解 $xy + 9 = 86 (x + y)$．

---

注意这个方程可以写成 $xy 9 + 9 x + y + 81 = 167$．现在 $167$是质数，左边可以被SFFT分解为 $(x + 9) (y + 9)$．现在自

$(x + 9) (y + 9) = 1 \ * 167 = 167 \ * 1 = (1) \ * (-167) = (-167) \ * (1),$

我们得到四个解

$(x, y) =(-8158),(158 8),(-10、-176),(-176,-10)。\ _ \广场$

求方程的所有积分解 $公元前2 b + 3 c = 5$．

---

也许你希望写作 $5 bc-2b-3c$在表单中

$5 bc-2b-3c = (5 b + *) (c + *) + *,$

或者类似的东西，每个 $＊$表示一个整数。不幸的是，这是不可能的。的 $5$碍事。我们可以通过整个表达式乘以5来消除这个困难

$\{对齐}开始25 bc-10b-15c& 25 bc-10b-15c + 6 = 0 \ \ & = 6 \ \(5酮(5 c - 2) & = 6。结束\{对齐}$

它只剩下检查整数对相乘得到6。我们检查每个

$(5酮- 5 c - 2) =(6, 1),(2),(2、3),(1,6),(6),(2、3),(2),(6,1)。$

其中,只有 $(2)$和 $(2、3)$导致 $b$和 $c$正整数。这些对对应于解 $(b, c) = (0,0)$或 $(b, c) = (1,1)$． $_ \广场$

这种技术是由AoPS用户Simon Rubinstein-Salzedo首次引入的。这就是为什么它被称为“西蒙最喜欢的保理技巧”。

求正整数解的有序对的个数 $(x, y)$来 $xy = 60$．

---

请注意, $x$的正除数是 $60$，对于每一个 $x$，有一种独特 $y = \压裂{60}{x}$．所以正整数有序对的个数 $(x, y)$满足方程的这个数就等于 $60$．

自 $60 = 2 ^ 2 \ 3 cdot \ cdot 5$，从除数函数， $60$有 $(2 + 1) (1 + 1) (1 + 1) = 12$积极的因数。

因此, $12$是我们问题的答案。 $_ \广场$

看到这有多简单了吗?虽然很简单，但这个问题证明了在解丢番图方程时因式分解的动机。

如果你有丢番图方程 $F (x_1, x_2, x_3， \cdots x_n)=0$你可以把它分解成等价的形式

$f (x_1、x_2, x_3 \ ldots x_n)₂(x_1、x_2 x_3, \ ldots x_n) \ cdots f_k (x_1、x_2 x_3, \ ldots x_n) = c,$

在哪里 $c$是整数吗，你要做的就是考虑除数 $c$并检查情况。

有时候有很多案件需要检查，你可以做一些事情来减少案件的工作量。

这就是因式分解的要点。把原来的方程写成这样一边是整数另一边是项的乘积。这将帮助你解很多丢番图方程。

分解技术最好通过大量的例子来理解。下面是一些例子!

解丢番图方程 $x - y ^ 4 = 4$,在那里 $x$是一个典型。

---

既然我们讨论了因式分解，我们看看有没有办法重新安排这些项并因式分解。

重新安排给我们

$x = y ^ 4 + 4 = (y ^ 2) ^ 2 + 2 ^ 2 = (y ^ 2 + 2) ^ 2 - 2 \ cdot y ^ 2 \ cdot 2 = (y ^ 2 + 2) ^ 2 - 2 y ^ 2。$

现在用平方差等式，我们可以把右边完全分解

$x = y (y ^ 2 + 2 + 2) (y ^ 2-2y + 2) = \大((y + 1) ^ 2 + 1大)\ \大((y-1) ^ 2 + 1 \大)。$

这对我们有什么帮助呢?

记住, $x$是质数。因此,如果 $x$可以表示为两个数的乘积，其中一个等于 $1$．幸运的是，右边的表达式告诉我们如果 $y | | \ neq1$,然后 $x$两个整数的乘积是否大于 $1$，不可能是质数。

所以，唯一可能的值 $y$是 $1$和 $－１$．把这些代入方程，就得到 $x = 5$．这意味着这个问题的唯一解是 $(5、1)$和 $(5、1)$． $_ \广场$

提示: $^ 4 + 4 b ^ 4$可以被分解成 $(^ 2-2ab b + 2 ^ 2) (^ 2 + 2 ab + 2 b ^ 2)$，被称为索菲·杰曼身份。

让我们看另一个例子。

找出整数的有序对的数目 $(a, b)$满足 $\压裂{1}{}+ \压裂{1}{b} = \压裂{1}{n},$在哪里 $n$为固定整数。

---

第一个自然反应是清除分母。让我们这样做，我们得到

$ab -十亿= 0。$

我们试着分解它，看看会发生什么:

$bn (b n) = 0。$

要是我们有另一个就好了 $n ^ 2$词……等等!如果我们想要 $n ^ 2$术语，为什么不引入呢?然后我们会有一些类似

$bn (b n) + n ^ 2 = n ^ 2。$

现在我们可以把它分解如下:

$(b n) - n (b n) =(一)(b n) = n ^ 2。\ qquad (1)$

这意味着 $(一)$的除数是 $n ^ 2$．还记得第一个问题吗?这个和那个很相似。但是现在我们还要处理负因子。这实际上使我们的工作更容易。

让 $\τ(n ^ 2)$的正因数的个数 $n ^ 2$．所以总的除数(正负)是 $n ^ 2$等于 $2 \τ(n ^ 2)$．这应该就是我们问题的答案，对吧?等等!请注意, $(0,0)$满足 $(1）$，但不满足原方程。所以我们要从计数中减去这个。

因此，我们的最终计数是 $2 \τ(n ^ 2) 1$． $_ \广场$