前前言

下面是记录的一些可能会用到的markdown数学公式语法，读者完全可以忽略掉这部分内容
$$
\epsilon \frac {1}{2} \equiv \mod{a} \pm \sum \prod \pmod{a}
\bull \Leftarrow \Leftrightarrow \Rightarrow \ne
$$

前言

最近在学密码学的数论知识，有些问题的证明在课程中没有讲到，在此我进行了自己的思考，并对某些问题给出证明过程，但是由于这些仅仅是本人独自思考的产物，因此可能显得非常随意，读者不要太过在意。

第一个问题：模运算下的除法化简（不是乘法逆元）

模运算中有以下结论：

现在有一个同余式：
$$
a\equiv b \pmod{n}
$$
假设a和b有公约数t,那么上面这个式子就可以进行化简

接下来分为两种情况：
$$
第一种情况：gcd(t,n)=1,也就是t和n互为素数时，有\
a//t \equiv b//t \pmod{n}\
第二种情况，gcd(t,n) \ne 1,也就是t和n不互为素数时，一定有\
a//t\equiv b//t \pmod{n//t}\
不一定有\
a//t \equiv b//t \pmod{n}\
$$
在这里给出笔者的证明过程

证明（以笔者的思考过程为线索）

首先讨论一下第二种情况下的必然情况，即
$$
a//t\equiv b//t \pmod{n//t}\
$$
我们可以将原来的式子展开
$$
a=kn+b
$$
其中t为a,b,n公共的因子，那么显然,两遍同时除以t，有
$$
a//t=k(n//t)+b//t
$$
那么第二种情况下的必然情况就可以证明了

于是现在就有问题，为什么第一种情况可以呢？如果我们将原来的式子展开
$$
a=kn+b
$$
此时t不是n的因子，如果要将两边同时除以t，那么只有可能是k被t除掉了，但是t|k这种情况不一定啊，直接在两边同时除以t怎么就可以了？？？

于是，我们接下来就应该要证明在t和n互为素数的情况下t一定整除k

emmmm

我们不妨从除法的逆运算——乘法开始探索一下？

我们知道模运算下乘法是显然成立的，即

我们假设有一个新的同余式
$$
a \equiv b \pmod{n}
$$
现在我们让等式两边同乘以m
$$
ma \equiv mb \pmod{n}
$$
我们把它展开看看
$$
ma = mkn+mb
$$
其中k是在原来的同余式展开的情况下n的系数

诶，如果把这里的ma ， mk ，mb都看做是a,k,b，那么不就是我们的第一种情况吗！

这里的m就看做我们最开始的那个t，那么第一种情况能够成立就非常显然了！

emmmm 但是当第一种情况的结论套在第二种情况下怎么就不一定了呢？

我们考虑，第一种情况下 的
$$
a \equiv b \pmod{n}
$$
其实可以看做是通过我们刚刚乘以m这个方式构造出来的，那么再除回去也很正常了，也就是说当t和n互为素数的情况下,n前面的系数k一定可以被t整除，如果k不能被t整除的话，那么就不可能出来这个同余式子，因为展开后等式两边没有共同的因子t，因此这个同余式就不可能被构造出来。

但是如果n和t是互为素数的情况下,这种情况就不一定了，等式两边的公共因子t可以被n提供，这样k就不必被t整除了，这也就是第一种情况的结论套用在第二种情况下不一定成立的原因了。

反思

这里的证明过程显然复杂了，但这是我自己的思考历程，其中在第一种情况下t|k这个条件完全可以直接的出来，但是我显然没有这种经验积累或者说是观察力，只能通过逆向分析才能得到。

这里就积累一个显然的结论：
$$
等式如果成立，且等式一边可以被某一个数整除，则等式另一边也必然可以被这个数整除，否则等式不成立。
$$

第二个问题

欧拉定理的证明中有这样一句话：
$$
Z_n ^* 中各个整数不同，乘以a并对n取模后仍然不同,其中gcd(a,n)=1
$$
这句话并不是很显然，但是课程中并没有进行证明，因此在此，我对这个问题进行一下证明

一些知识

  1. $$
    Z_n ^* 是什么？\
    Z_n ^*是在1到n之间与n互为素数的数的集合
    $$
    显然，在这个集合中各个元素互不相同，这些元素乘以与n互为素数的a后的值仍然互不相同，也就是说，这形成了一个双射。

证明

这里要用到我们之前积累的结论了：

*** 等式如果成立，且等式一边可以被某一个数整除，则等式另一边也必然可以被这个数整除，否则等式不成立。***

这个问题等价于下面这个问题
$$
a,b \epsilon Z_n^* ,当gcd(t,n)=1时，\
at\equiv bt \pmod{n}不成立
$$
将这个同余式展开得到
$$
at=bt+kn
$$
其中gcd(a,n)=1,gcd(b,n)=1

显然等式左边可以被t或者t的因子整除，那么等式右边也应该能被t或者t的因子整除，但是我们知道gcd(t,n)=1，也就是说kn这一项无论如何也不能被t或者t的因子整除，那么这个式子就不成立，也就是说原结论必然成立。

反思

在这里进行思考的时候，我已经对上面那个问题进行了分析，但是没有总结出显而易见的结论，从而导致在这个题的时候我其实是又进行了一遍分析，最后在写博客的时候才发现原来用上第一个问题得出的结论就能够出来答案。

也就是说，其实这个结论还挺显然的……