99 - 數論

試題查詢 http://www1c.moex.gov.tw/main/exam/wFrmExamQandASearch.aspx?menu_id=156

一、將 $540792$ 分解成質數的乘積。

二、試求 $6497$ 與 $11899$ 的最大公因數。

三、試求方程式 $29x-19y=5$ 的最小正整數解，再利用最小正整數解寫出此方程式的所有整數解。

四、已知 $729=27^2$、$71289=267^2$。試證：$71111288889$ 等於某個正整數的平方。

五、已知：$$
\begin{aligned}
&3^2+4^2+5^2=0^2+1^2+7^2 \\
&6^2+7^2+8^2=1^2+2^2+12^2 \\
&9^2+10^2+11^2=2^2+3^2+17^2
\end{aligned}
$$試對正整數 $n$ 寫出一個等式，使得：該等式在 $n=1$ 時就是上述第一式，在 $n=2$ 時就是上述第二式，在 $n=3$ 時就是上述第三式。並證明所寫等式對每個正整數 $n$ 都成立。

六、試證：若 $n$ 是大於 $9$ 的正整數，而且 $n-4$、$n-2$、$n+2$、$n+4$ 都是質數，則 $n$ 必是 $15$ 的倍數。並寫出滿足此假設條件的兩個最小正整數 $n$。

七、設 $n$ 等於兩個相異質數 $p$ 與 $q$ 的乘積。已知 $n$ 的所有正因數之和為 $768$，而小於 $n$ 且與 $n$ 互質的正整數共有 $660$ 個，試求 $n$ 的值。

八、試找出滿足下述條件的所有整數 $n$：$$9n\equiv 8\mbox{ (mod 13)}，11n\equiv -4\mbox{ (mod 12)}，0\leq n \leq 500$$請注意：所謂 $9n\equiv 8\mbox{ (mod 13)}$，乃是表示 $9n-8$ 是 $13$ 的倍數。

---

解題

一、
$540792=2^3\times 3^2\times 7\times 29\times 37$

二、
Greatest Common Divisor (GCD) for $6497$, $11899$ is $73$.

三、
最小正整數解 $(x_0,y_0)=(10,15)$，全部解$\left\{\begin{matrix}
x=10+19t\\
y=15+29t
\end{matrix}\right.,\; t\in \mathbb{Z}$

四、
觀察 $1$ 和 $8$ 有四個，答案是 $266667$.

五、
$(n+2)^2+(n+3)^2+(n+4)^2=(n-1)^2+n^2+(5n+2)^2$

六、
如果 $n\equiv 1\mbox{ mod($3$)}$，則 $n-4$、$n-2$、$n+2$、$n+4$ 除以 $3$ 的最小正剩餘分別為 $0$、$2$、$0$、$2$，表示其中 $n-4$ 和 $n+2$ 皆可被 $3$ 整除，與題目所設四數皆為質數矛盾，故 $n\not \equiv 1\mbox{ mod($3$)}$。

若 $n\equiv 2\mbox{ mod($3$)}$，四數之最小正剩餘分別為 $1$、$0$、$1$、$0$，表示其中 $n-2$ 和 $n-4$ 可被 $3$ 整除。

若 $n\equiv 0\mbox{ mod($3$)}$，四數之最小正剩餘分別為 $2$、$1$、$2$、$1$。

同理，若 $n\not \equiv 0\mbox{ mod($5$)}$，四數之最小正剩餘中，其中必有一為 $0$，即當中會有一個數是 $5$ 的倍數，與題目所述矛盾。當 $n\equiv 0\mbox{ mod($5$)}$，四數之最小正剩餘分別為 $1$、$3$、$2$、$1$。

因為 $3\mid n$，$5\mid n$，所以 $15\mid n$。

當 $n=15$，$\left\{\begin{matrix}
n-4=11\\
n-2=13\\
n+2=17\\
n+4=19
\end{matrix}\right.$

當 $n=7\times 15=105$，$\left\{\begin{matrix}
n-4=101\\
n-2=103\\
n+2=107\\
n+4=109
\end{matrix}\right.$

所以兩個最小的 $n$ 為 $15$ 和 $105$。

七、
正因數的和 $=(p^0+p^1)(q^0+q^1)=1+p+q+pq=768$；Euler's phi function $\varphi (n)=\varphi (pq)=\varphi (p)\varphi (q)=(p-1)(q-1)=660$。解 $pq=n=713$。

八、
$x\equiv 76\mbox{ (mod $156$)}$