����� I No.14����

���� 14.1   $a=7046, b=1781$ �Ȥ����� �Ľ�Ʊ��

$$\varphi:{\mbox{${\mathbb{Z}}$}}\to {\mbox{${\mathbb{Z}}$}}/a{\mbox{${\mathbb{Z}}$}}\times {\mbox{${\mathbb{Z}}$}}/b{\mbox{${\mathbb{Z}}$}}$$

�ˤĤ��ơ�

1. ���Τ褦�ʤ�Τ����ä��Ȥ��ơ� $\varphi(n)$ ����ʤ�����
2. ��ξ����������Ľ�Ʊ�� $\varphi$ ��¸�ߤ��뤳�Ȥ򼨤��ʤ�����
3. $d=\gcd(a,b)$ ($a,b$ �κ�������)����ʤ�����
4. $\operatorname{Ker}(\varphi)$ ����ʤ�����
5. $\varphi(n)=([5 d]_a, [6 d]_b)$ �������� $n$ �� ���Ƶ��ʤ�����

��Ϣ����׻�

$$7046/1781=3.95...\approx 4$$

$$7046-1781\times 4=-78$$

$$1781 /78=22.83...\approx 23$$

$$1781 -78 \times 23 =-13$$

$$78=13\times 6$$

$$\begin{pmatrix}7046 \\ 1781 \end{pmatrix} = \begin{pmatrix}4 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix}1781\\ -78 \end{pmatrix}$$

$$= \begin{pmatrix}4 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix}-23& 1\\ 1 & 0 \end{pmatrix} \begin{pmatrix}-78\\ -13 \end{pmatrix}$$

$$= \begin{pmatrix}4 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix}-23& 1... ...\begin{pmatrix}6& 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix}-13\\ 0 \end{pmatrix}$$

���Τ��Ȥ��顢

$$\begin{pmatrix}-13\\ 0 \end{pmatrix} = \begin{pmatrix}0& 1 \\ 1 & -6 \end{pmatrix} \begin{pmatrix}0& 1 \... ...{pmatrix}0& 1 \\ 1 & -4 \end{pmatrix} \begin{pmatrix}7046 \\ 1781 \end{pmatrix}$$

$$= \begin{pmatrix}23 & -91 \\ -137 & 542 \end{pmatrix} \begin{pmatrix}7046 \\ 1781 \end{pmatrix}$$

�������롣 ��1�󤫤�

$$23 \times 7046 +(-91)\times 1781=-13$$ (��)

�������롣

$$7046=13 \times 542 , \quad 1781=13 \times 137$$ (��)

�Ǥ��뤳�Ȥ��顢$13$ �� $a,b$ �θ�����Ǥ��뤳�Ȥ��狼�롣 ¾���ǡ�(��)���顢$7046$ �� $1781$ ��ɬ��Ū�� $13$ ������Ǥ��뤳�Ȥ� �狼�뤫�顢$13$ �� $7046$ �� $1781$ �κ��������� $13$ �Ǥ��롣