# 台大 106 數學
###### tags: `NTU` `106` `數學`
1. $\begin{pmatrix}1&0&1\\r&1&r\\3&r&2\end{pmatrix}$
2. 1
3. $\frac{1}{x^2+y^2}\begin{pmatrix}x^2&xy\\xy&y^2\end{pmatrix}$
:::info
對於任意向量 $u$，只需要扣掉在 $\begin{pmatrix}y\\-x\end{pmatrix}$ 的投影，就會變成在 $\begin{pmatrix}x\\y\end{pmatrix}$ 的投影。令 $v=\begin{pmatrix}y\\-x\end{pmatrix}$
$$
u-\frac{v^Tu}{v^Tv}v=\\u-\frac{vv^T}{v^Tv}u=\\(I-\frac{vv^T}{v^Tv})u
$$
$I-\frac{vv^T}{v^Tv}$ 即為所求
:::
4. $\pm\frac{1}{\sqrt{3}}\begin{pmatrix}1\\1\end{pmatrix}$
5. $\begin{pmatrix}1&1&1&1\\1&0&-2&1\\1&-1&1&1\end{pmatrix}$
6. $2^{m^2}-2^{m^2-m+1}$
7. $(p\ \wedge\ r)\vee\ (!p\ \wedge\ q)$
8.
$$
A=2a_1+(\sqrt{5}-1)a_0\\
B=1+\sqrt{5}\\C=-2a_1+(\sqrt{5}+1)a_0\\D=1-\sqrt{5}
$$
9.
- 對於任意兩正整數 $a, b$，令 $S=\{ax+by\ |\ x,y\in Z\}$。則 S 中最小的正整數即為 $a,b$ 的最大公因數
:::info
proof:
gcd(a,b) 滿足
- gcd(a,b) | a 且 gcd(a,b) | b
- 對於任意 c | a 且 c | b，滿足 c | gcd(a,b)

令 c = ax+by 為 S 中最小的正整數。則 a = tc+q = t(ax+by)+q
移項得 q = a(1-tx)-by。可知 q 也是 S 的一員，且因為 q 是 c 除 a 的餘數，可知 $0\le q\lt c$。但因為 c 是 S 中最小的正整數，可得 q = 0，也就是說，c 整除 a。

用同樣的步驟可推得 c 整除 b。

再來，對於任意 a, b 的公因數 d，d 一定能整除 a 和 b 的線性組合，所以一定能整除 c。

Q.E.D
:::
利用上述定理，只需要知道 $S=\{(n-1)x+ny\ |\ x,y\in Z\}$ 中最小的正整數，就可知道最大公因數。不難發現令 x = -1, y = 1 即可算出最小為 1，也就是說 n - 1 和 n 的最大公因數為 1，代表兩數互質。

10. bipartite
11. $2^{n-1}$