数学基础-作业二

2022/11/23 Math 共 3250 字,约 10 分钟

$\text{Question}\ 1$

$\text{Description}\ 1$

求 $GF_2[x]$ 上多项式 $f(x)=x^5+x^3+x+1$ 与 $g(x)=x^3+x^2+x+1$ 的最大公因式,并求出多项式 $s(x),t(x)$,使得 $s(x)f(x) + t(x)g(x) = \gcd(f(x),g(x))$,且 $s(x)$ 和 $t(x)$ 的次数分别小于 $g(x)$ 和 $f(x)$ 的次数。

$\text{Answer}\ 1$

\[\begin{align} \text{let}\ &f_1(x)=f(x),\ g_1(x)=g(x)\\ &f_1(x)=q_1(x)g_1(x)+r_1(x)\rightarrow q_1(x)=x^2+x+1,\ r_1(x)=x^2+x\\ \text{let}\ &f_2(x)=g_1(x),\ g_2(x)=r_1(x)&\\ &f_2(x)=q_2(x)g_2(x)+r_2(x)\rightarrow q_2(x)=x,\ r_2(x)=x+1\\ \text{let}\ &f_3(x)=g_2(x),\ g_3(x)=r_2(x)&\\ &f_3(x)=q_3(x)g_3(x)+r_3(x)\rightarrow q_3(x)=x,\ r_3(x)=0\\ \text{then:} &\gcd(f(x),g(x))=g_3(x)=x+1\\ g_3(x)&=f_2(x)+q_2(x)g_2(x)\\ &=g_1(x)+r_1(x)q_2(x)\\ &=g_1(x)+[f_1(x)-g_1(x)q_1(x)]q_2(x)\\ &=g_2(x)f_1(x)+[q_1(x)q_2(x)+1]g_1(x)\\ \text{so}\ &s(x)=q_2(x)=x,\ t(x)=[q_1(x)q_2(x)+1]=x^3+x^2+x+1\\ \end{align}\]

$\text{Question}\ 2$

$\text{Description}\ 2$

计算 $8$ 元域 $GF_2[x]/(x^3+x+1)$ 的加法表和乘法表

$\text{Answer}\ 2$

元素集合: ${0,1,x,1+x,x^2,1+x^2,x+x^2,1+x+x^2}$

加法表

$+$$0$$1$$x$$1+x$$x^2$$1+x^2$$x+x^2$$1+x+x^2$
$0$$0$$1$$x$$1+x$$x^2$$1+x^2$$x+x^2$$1+x+x^2$
$1$$1$$0$$1+x$$x$$1+x^2$$x^2$$1+x+x^2$$x+x^2$
$x$$x$$1+x$$0$$1$$x+x^2$$1+x+x^2$$x^2$$1+x^2$
$1+x$$1+x$$x$$1$$0$$1+x+x^2$$x+x^2$$1+x^2$$x^2$
$x^2$$x^2$$1+x^2$$x+x^2$$1+x+x^2$$0$$1$$x$$1+x$
$1+x^2$$1+x^2$$x^2$$1+x+x^2$$x+x^2$$1$$0$$1+x$$x$
$x+x^2$$x+x^2$$1+x+x^2$$x^2$$1+x^2$$x$$1+x$$0$$1$
$1+x+x^2$$1+x+x^2$$x+x^2$$1+x^2$$x^2$$1+x$$x$$1$$0$

乘法表

$\times$$0$$1$$x$$1+x$$x^2$$1+x^2$$x+x^2$$1+x+x^2$
$0$$0$$0$$0$$0$$0$$0$$0$$0$
$1$$0$$1$$x$$1+x$$x^2$$1+x^2$$x+x^2$$1+x+x^2$
$x$$0$$x$$x^2$$x+x^2$$1+x$$1$$1+x+x^2$$1+x^2$
$1+x$$0$$1+x$$x+x^2$$1+x^2$$1+x+x^2$$x^2$$1$$x$
$x^2$$0$$x^2$$1+x$$1+x+x^2$$x+x^2$$x$$1+x^2$$1$
$1+x^2$$0$$1+x^2$$1$$x^2$$x$$1+x+x^2$$1+x$$x+x^2$
$x+x^2$$0$$x+x^2$$1+x+x^2$$1$$1+x^2$$1+x$$x$$x^2$
$1+x+x^2$$0$$1+x+x^2$$1+x^2$$x$$1$$x+x^2$$x^2$$1+x$

二进制乘法代码

void mul(const bitset<10> &a, const bitset<10> &b) {
    bitset<10> result(0);
    for (int i = 9; i >= 6; i--) {
        if (b[9-i]) {
            result ^= (a << (9 - i));
        }
    }
    for (int i = 2; i <= 6; i++) {
        if(result[9-i]) {
            result ^= (base << (6 - i));
        }
    }
    pt(&result);
}

$\text{Question}\ 3$

$\text{Description}\ 3$

令 $G$ 为群,$e$ 是群 $G$ 中的单位元。$a\in G$,且 $a$ 的阶等于 $n$,即 $ord(a)=n$,证明:集合 $H={e,a,a^2,\cdots, a^{n-1}}$ 为 $G$ 的子群。

$\text{Answer}\ 3$

  1. 首先证明 $H$ 是群 $G$ 的子集
    • $a$ 的阶等于 $n$,所有 $a^n=e$
    • $H={a^t \mid 1\le t \le n} \subseteq G$
  2. 证明 $H$ 是一个群
    • 首先集合 $H$ 中存在单位元 $e$
    • 对于任意 $x=a^{t},x\not=e$,有 $a^ta^{n-t}=e,a^{n-t}\in H$,故每个元素都有逆元
    • 对于任意 $x=a^{t_1},y=a^{t_2}$,$xy=a^{t_1+t_2}$,$2 \le t_1+t_2 \le 2n$
    • 当 $2 \le t_1+t_2 \le n$ 时,$a^{t_1+t_2}\in H$,当 $n+1 \le t_1+t_ 2 \le 2n$ 时,$a^{t_1+t_2}=a^{t_1+t_2-n}\in H$,即运算封闭
  3. 故 $H$ 是群 $G$ 的子群

$\text{Question}\ 4$

$\text{Description}\ 4$

证明 $p^{q-1}+q^{p-1}\equiv1 \pmod{pq}$,这里 $p,q$ 是不同的素数。

$\text{Answer}\ 4$

  1. 由欧拉定理,有 $p^{q-1}\equiv 1 \pmod q,q^{p-1}\equiv 1 \pmod p$
  2. 又有$q^{p-1}\equiv 0 \pmod q,p^{q-1}\equiv 0 \pmod p$
  3. 即 $p^{q-1}+q^{p-1}\equiv1 \pmod{p},p^{q-1}+q^{p-1}\equiv1 \pmod{q}$
  4. 则 $p^{q-1}+q^{p-1}\equiv1 \pmod{\text{gcm}(p,q)=pq}$

$\text{Question}\ 5$

$\text{Description}\ 5$

计算 $2^{2022118} \pmod7$。

$\text{Answer}\ 5$

  1. $2^{\varphi(7)}\equiv1 \pmod 7 \rightarrow 2^6\equiv1 \pmod7$
  2. $2022118\%6=4$
  3. $2^{2022118}\equiv2^4\equiv2 \pmod7$

$\text{Question}\ 6$

$\text{Description}\ 6$

计算 $17$ 模 $48$ 的指数 $\text{ord}_{48}(17)$。

$\text{Answer}\ 6$

  1. $\varphi(48)=\varphi(2^43^1)=48(1-\frac{1}{2})(1-\frac{1}{3})=16$
  2. 考虑 $16$ 的所有因子 $1,2,4,8,16$
  3. $17^2\%48=1$,故$\text{ord}_{48}(17)=2$

文档信息

Search

    Table of Contents