1. Division Algorithm with Remainder

Let \(a,b\) be integers with \(a\neq0\). Then there exist unique integersq and r such that:

\(\boldsymbol{b=aq+r,\quad 0\le r<|a|}\)

• q: the quotient when b is divided by a
• r: the remainder when b is divided by a

2. Divisibility

• If \(\boldsymbol{r=0}\): b is divisible by a (or a divides b), denoted by \(\boldsymbol{a\mid b}\).
• If \(\boldsymbol{r\neq0}\): b is not divisible by a (or a does not divide b), denoted by \(\boldsymbol{a\nmid b}\).

Attention:

(-10) / (-3) => -10=(-3)*4 +2, the reminder is 2, not -1

\(a\mid b \iff a\mid (-b) \iff (-a)\mid b \iff (-a)\mid (-b) \iff |a|\mid |b|\)

Divisibility holds for integers, their negatives, and their absolute values equivalently.

For any non‑zero integer a: \(1\mid a\), \(a\mid a\), \(a\mid 0\).

1 divides every non‑zero integer; every non‑zero integer divides itself and 0.

If \(a\mid b\) and \(b\mid c\), then \(a\mid c\).

Divisibility is transitive.

If \(a\mid b\) and \(c\mid d\), then \(ac\mid bd\).

Divisibility is preserved under multiplication of divisors and dividends.

If \(a\mid b\) and k is a natural number, then \(a^k\mid b^k\).

Divisibility is preserved under exponentiation by the same natural number.

If \(a\mid b\), \(a\mid c\), and \(m,n\) are integers, then \(a\mid (mb+nc)\).

⚠️💥⚠️⚠️💥⚠️⚠️💥⚠️⚠️💥⚠️

If a divides two integers, it divides any integer linear combination of them.

If \(a\mid b\) and \(b\neq0\), then \(1\le|a|\le|b|\).

⚠️💥⚠️⚠️💥⚠️⚠️💥⚠️⚠️💥⚠️

The absolute value of a non‑zero divisor is no larger than that of its dividend.

If \(a\mid b\) and \(b\mid a\), then \(a=\pm b\).

Two integers dividing each other must be equal or negatives of each other.

带余除法与整除

1. 带余除法

设 \(a,b\) 为整数，且 \(a\neq0\)，则存在唯一的一对整数 q 和 r，满足：

\(\boldsymbol{b=aq+r,\quad 0\le r<|a|}\)

• q：b 被 a 除所得的商
• r：b 被 a 除所得的余数

2. 整除

• 若余数 \(\boldsymbol{r=0}\)：称 b 能被 a 整除（a 整除 b），记作 \(\boldsymbol{a\mid b}\)
• 若余数 \(\boldsymbol{r\neq0}\)：称 b 不能被 a 整除（a 不整除 b），记作 \(\boldsymbol{a\nmid b}\)

整除的性质（Properties of Divisibility）

1. \(a\mid b \iff a\mid (-b) \iff (-a)\mid b \iff (-a)\mid (-b) \iff |a|\mid |b|\)一个整数整除另一个整数，等价于其相反数、绝对值之间的整除关系。
2. 对任意非零整数 a，有：\(1\mid a\)，\(a\mid a\)，\(a\mid 0\)1 整除任意非零整数；任意非零整数整除自身；任意非零整数整除 0。
3. 若 \(a\mid b\)，\(b\mid c\)，则 \(a\mid c\)整除具有传递性。
4. 若 \(a\mid b\)，\(c\mid d\)，则 \(ac\mid bd\)整除式相乘，保持整除关系。
5. 若 \(a\mid b\)，k 为自然数，则 \(a^k\mid b^k\)整除关系可同步乘方。
6. 若 \(a\mid b\)，\(a\mid c\)，\(m,n\) 为整数，则 \(a\mid (mb+nc)\)整除两数，则整除两数的任意整数线性组合。
7. 若 \(a\mid b\)，\(b\neq0\)，则 \(1\le|a|\le|b|\)非零数的约数的绝对值不大于自身的绝对值。
8. 若 \(a\mid b\)，\(b\mid a\)，则 \(a=\pm b\)两数互相整除，则两数相等或互为相反数。

---

Q1

Given positive integers \(x,y\) with \(\boldsymbol{\gcd(x,y)=1}\) and \(xy\neq1\), and m a positive even integer. Prove that \(\boldsymbol{x+y \nmid x^m+y^m}\).

已知正整数 \(x,y\) 满足 \(\boldsymbol{\gcd(x,y)=1}\) 且 \(xy\neq1\)，m 为正偶数，求证：\(\boldsymbol{x+y\nmid x^m+y^m}\)。

步骤 1：推导基础整除关系

因为 n 是正偶数，对 \(x^n-y^n\) 因式分解：

\(x^n-y^n=(x^2)^{\frac{n}{2}}-(y^2)^{\frac{n}{2}}\)

由平方差整除性质，\(x^2-y^2 \mid x^n-y^n\)，

又 \(x^2-y^2=(x+y)(x-y)\)，因此

\(\boldsymbol{x+y \mid x^n-y^n}\)

步骤 2：反证法假设

假设 \(x+y \mid x^n+y^n\)。

步骤 3：利用整除的可加性

由整除性质：若除数整除两个数，则整除两数之和，因此

\(x+y \mid (x^n+y^n)+(x^n-y^n)=2x^n\)

步骤 4：利用互质性推导

已知 \(\gcd(x,y)=1\)，由辗转相除法：

\(\gcd(x+y,x)=\gcd(y,x)=1\)

故 \(\boldsymbol{\gcd(x+y,x^n)=1}\)。

步骤 5：缩小范围推出矛盾

因为 \(x+y \mid 2x^n\) 且 \(\gcd(x+y,x^n)=1\)，得

\(x+y \mid 2 \implies x+y\le2\)

又 \(x,y\) 为正整数且 \(xy\neq1\)，则 \(x+y\ge1+2=3>2\)，矛盾。

因此假设不成立，故 \(\boldsymbol{x+y \nmid x^n+y^n}\)。

---

Proof in English

Step 1: Derive basic divisibility relation

Since n is a positive even integer, factorize \(x^n-y^n\):

\(x^n-y^n=(x^2)^{\frac{n}{2}}-(y^2)^{\frac{n}{2}}\)

By divisibility property of difference of squares, \(x^2-y^2 \mid x^n-y^n\).

Since \(x^2-y^2=(x+y)(x-y)\), we get

\(\boldsymbol{x+y \mid x^n-y^n}\)

Step 2: Proof by contradiction

Assume \(x+y \mid x^n+y^n\).

Step 3: Additive property of divisibility

If a divisor divides two numbers, it divides their sum. Thus

\(x+y \mid (x^n+y^n)+(x^n-y^n)=2x^n\)

Step 4: Coprimality deduction

Given \(\gcd(x,y)=1\), by the Euclidean algorithm:

\(\gcd(x+y,x)=\gcd(y,x)=1\)

Hence \(\boldsymbol{\gcd(x+y,x^n)=1}\).

Step 5: Contradiction

Since \(x+y \mid 2x^n\) and \(\gcd(x+y,x^n)=1\), we have

\(x+y \mid 2 \implies x+y\le2\)

As \(x,y\) are positive integers with \(xy\neq1\), \(x+y\ge1+2=3>2\), which is a contradiction.

Thus the assumption is false, so \(\boldsymbol{x+y \nmid x^n+y^n}\).

---

Q2

Find all positive integers \(a,b,c\) with \(a<b<c\), such that for any two numbers, their product plus 1 is divisible by the third one.

求所有正整数 \(a,b,c\)（\(a<b<c\)），使得其中任意两个数的乘积加 1 都能被第三个数整除。

推导核心整除关系由题意，\(a\mid bc+1,\ b\mid ac+1,\ c\mid ab+1\)，根据整除性质：\(abc\mid (bc+1)(ca+1)(ab+1)\)展开右侧：\((bc+1)(ca+1)(ab+1)=a^2b^2c^2+abc(a+b+c)+ab+bc+ac+1\)因为 \(abc\mid a^2b^2c^2,\ abc\mid abc(a+b+c)\)，故：\(\boldsymbol{abc\mid ab+bc+ac+1}\)

确定 a 的取值由 \(abc \le ab+bc+ac+1\)，且 \(a<b<c\)，得：\(ab+bc+ac+1<3bc+1 \implies abc\le3bc \implies a\le3\)排除 \(a=3\)（无正整数解），故 \(a=1\) 或 \(a=2\)。

情况 1：\(a=1\)代入得：\(bc\mid b+c+1\)，即 \(bc\le b+c+1\)变形：\((b-1)(c-1)\le2\)由 \(1<b<c\)，得 \(b=2,\ c=3\)。验证：\(1\mid 2\times3+1,\ 2\mid1\times3+1,\ 3\mid1\times2+1\)，成立。

情况 2：\(a=2\)代入得：\(2bc\mid bc+2b+2c+1\)，即 \(2bc\le bc+2b+2c+1\)变形：\((b-2)(c-2)\le5\)由 \(2<b<c\)，得 \(b=3,\ c=7\)。验证：\(2\mid3\times7+1,\ 3\mid2\times7+1,\ 7\mid2\times3+1\)，成立。

最终解

\(\boldsymbol{(1,2,3),\ (2,3,7)}\)

---

English

Problem

Find all positive integers \(a,b,c\ (a<b<c)\) such that

\(a\mid bc+1,\ b\mid ac+1,\ c\mid ab+1\)

Solution

1. Derive core divisibilityGiven \(a\mid bc+1,\ b\mid ac+1,\ c\mid ab+1\), we have\(abc\mid (bc+1)(ca+1)(ab+1)\)Expand the product:\((bc+1)(ca+1)(ab+1)=a^2b^2c^2+abc(a+b+c)+ab+bc+ac+1\)Since abc divides the first two terms, we get\(\boldsymbol{abc\mid ab+bc+ac+1}\)
2. Restrict value of aFrom \(abc \le ab+bc+ac+1\) and \(a<b<c\):\(ab+bc+ac+1<3bc+1 \implies abc\le3bc \implies a\le3\)\(a=3\) gives no valid positive integers, so \(a=1\) or \(a=2\).
3. Case 1: \(a=1\)\(bc\mid b+c+1 \implies (b-1)(c-1)\le2\)With \(1<b<c\), we get \(b=2,\ c=3\). Verified.
4. Case 2: \(a=2\)\(2bc\mid bc+2b+2c+1 \implies (b-2)(c-2)\le5\)With \(2<b<c\), we get \(b=3,\ c=7\). Verified.

Final Solutions

\(\boldsymbol{(1,2,3),\ (2,3,7)}\)

---

Q3

Find all pairs of positive integers \((a,b)\) such that \(\boldsymbol{ab^2+b+7}\) divides \(\boldsymbol{a^2b+a+b}\).

试确定使 \(\boldsymbol{ab^2+b+7}\) 整除 \(\boldsymbol{a^2b+a+b}\) 的全部正整数对 \((a,b)\)。

步骤 1：利用整除性质

记 \(D=ab^2+b+7,\ N=a^2b+a+b\)。

由整除性质：\(D\mid bN-aD\)，计算得： \(\begin{align*} b(a^2b+a+b)-a(ab^2+b+7)&=b^2-7a \end{align*}\)

因此核心结论：

\(\boldsymbol{ab^2+b+7\mid b^2-7a}\)

步骤 2：分类讨论

情况 1：\(\boldsymbol{b^2-7a=0}\)

即 \(\boldsymbol{a=\dfrac{b^2}{7}}\)。

因为 a 为正整数，故 \(7\mid b\)，设 \(\boldsymbol{b=7k\ (k\in\mathbb{N}^*)}\)，则 \(\boldsymbol{a=7k^2}\)。

验证整除性： \(\begin{align*} D&=ab^2+b+7=7k^2\cdot(7k)^2+7k+7=7(49k^4+k+1)\\ N&=a^2b+a+b=(7k^2)^2\cdot7k+7k^2+7k=7k(49k^4+k+1) \end{align*}\)

因此 \(\dfrac{N}{D}=k\)，为整数。

故对任意正整数 k，\((7k^2,7k)\) 都是解。

情况 2：\(\boldsymbol{b^2-7a\neq0}\)

除数整除非零整数，故 \(ab^2+b+7\le|b^2-7a|\)。

• 若 \(b^2-7a>0\)：左边恒正，无解；
• 若 \(b^2-7a<0\)：即 \(a>\dfrac{b^2}{7}\)，代入不等式化简：
  • \(\boldsymbol{b=1}\)：\(a+8\mid a^2+a+1 \implies a+8\mid57\)，得 \(\boldsymbol{(11,1),(49,1)}\)；
  • \(\boldsymbol{b\ge2}\)：无正整数解。

全部解

\(\boldsymbol{(11,1),\ (49,1),\ (7k^2,7k)\quad(k\in\mathbb{N}^*)}\)

---

Complete Solution in English (Revised)

Step 1: Divisibility manipulation

Let \(D=ab^2+b+7,\ N=a^2b+a+b\).

By divisibility rules: \(D\mid bN-aD\). \(b(a^2b+a+b)-a(ab^2+b+7)=b^2-7a\)

Thus

\(\boldsymbol{ab^2+b+7\mid b^2-7a}\)

Step 2: Case analysis

Case 1: \(\boldsymbol{b^2-7a=0}\)

Then \(a=\dfrac{b^2}{7}\). Since \(a\in\mathbb{N}^*\), \(7\mid b\).

Let \(b=7k\ (k\in\mathbb{N}^*)\), then \(a=7k^2\).

Verification: \(\begin{align*} D&=7(49k^4+k+1)\\ N&=7k(49k^4+k+1) \end{align*}\)

\(\dfrac{N}{D}=k\in\mathbb{N}^*\), so \((7k^2,7k)\) is a solution for all positive integers k.

Case 2: \(\boldsymbol{b^2-7a\neq0}\)

Since \(ab^2+b+7\le|b^2-7a|\):

• \(b^2-7a>0\): No solutions;
• \(b^2-7a<0\):
  • \(b=1\): \(a+8\mid57\), giving pairs \(\boldsymbol{(11,1),(49,1)}\);
  • \(b\ge2\): No solutions.

All solutions

\(\boldsymbol{(11,1),\ (49,1),\ (7k^2,7k)\ \forall\ k\in\mathbb{N}^*}\)

---

Given any integer \(\boldsymbol{n\ge2}\), prove that there exist n distinct positive integers such that the sum of any two of them divides the product of all these n numbers.

任给整数 \(\boldsymbol{n\ge2}\)，证明：存在 n 个互不相同的正整数，使得其中任意两个数的和整除这 n 个数的乘积。

步骤 1：构造数集

取 n 个正整数：

\(\boldsymbol{a_i = i\cdot(2n-1)!,\quad i=1,2,\dots,n}\)

由于 \(1,2,\dots,n\) 互不相同，\((2n-1)!\) 为固定正整数，因此 \(a_1,a_2,\dots,a_n\)两两互不相同。

步骤 2：计算任意两数之和

任取 \(1\le i<j\le n\)： \(a_i+a_j = i\cdot(2n-1)!+j\cdot(2n-1)! = \boldsymbol{(i+j)\cdot(2n-1)!}\)

由 \(1\le i<j\le n\)，得 \(2\le i+j\le 2n-1\)，根据阶乘性质：

\(\boldsymbol{i+j \mid (2n-1)!}\)

因此： \(a_i+a_j=(i+j)\cdot(2n-1)! \mid \boldsymbol{\big[(2n-1)!\big]^2}\)

步骤 3：验证整除乘积

这 n 个数的乘积为： \(\prod_{k=1}^n a_k=\prod_{k=1}^n \big[k\cdot(2n-1)!\big]=n!\cdot\big[(2n-1)!\big]^n\)

显然 \(\big[(2n-1)!\big]^2 \mid n!\cdot\big[(2n-1)!\big]^n\)，故：

\(\boldsymbol{a_i+a_j \mid \prod_{k=1}^n a_k}\)

即任意两数之和整除 n 个数的乘积，命题得证。

---

Proof in English (Official Construction Method)

Step 1: Construct the number set

Define n positive integers:

\(\boldsymbol{a_i = i\cdot(2n-1)!,\quad i=1,2,\dots,n}\)

Since \(1,2,\dots,n\) are distinct and \((2n-1)!\) is a fixed positive integer, \(a_1,a_2,\dots,a_n\) are mutually distinct.

Step 2: Compute the sum of any two numbers

For any \(1\le i<j\le n\): \(a_i+a_j = i\cdot(2n-1)!+j\cdot(2n-1)! = \boldsymbol{(i+j)\cdot(2n-1)!}\)

Since \(2\le i+j\le 2n-1\), by the property of factorial:

\(\boldsymbol{i+j \mid (2n-1)!}\)

Thus: \(a_i+a_j=(i+j)\cdot(2n-1)! \mid \boldsymbol{\big[(2n-1)!\big]^2}\)

Step 3: Verify divisibility of the product

The product of all n numbers: \(\prod_{k=1}^n a_k=\prod_{k=1}^n \big[k\cdot(2n-1)!\big]=n!\cdot\big[(2n-1)!\big]^n\)

Clearly \(\big[(2n-1)!\big]^2 \mid n!\cdot\big[(2n-1)!\big]^n\), so:

\(\boldsymbol{a_i+a_j \mid \prod_{k=1}^n a_k}\)

The sum of any two numbers divides the product of all n numbers. The proof is complete.