next up previous
�U�@��: Congruence Equations �W�@��: Congruences �e�@��: Euler's Theorem

Wilson's Theorem

�� p �O�@�ӽ�Ʈ�, �Y p$ \nmid$a, �h Fermat's Little Theorem �i�D�ڭ� ap - 2 �b modulo p ���U�O a �����k�Ϥ���. ���M a �����k�Ϥ����b modulo p ���U�O�ߤ@��, Wilson's Theorem ���F�ڭ̦b modulo p ���U a �����k�Ϥ������t�@�ت��k.

���w m $ \in$ $ \mathbb {N}$, �����N�M m ���誺��� a, �� Proposition 3.2.5 �����i�H���@�өM m ���誺��� b �ϱo ab $ \equiv$ 1(mod m), �ڭ̤]�������M�o�˪� b �ä��ߤ@, ���b modulo m ���������U���|�O�ߤ@��. �]�N�O���u���b���H m ���U�M b �P�l����Ƥ~�|�ŦX. �o�ئb modulo m ���U���k�Ϥ������s�b�ߤ@�ʥ� modulo m ���U�� reduced residue system �̮e�����F.

Lemma 3.4.1   ���w m $ \in$ $ \mathbb {N}$, ���] S = {r1,..., r$\scriptstyle \phi$(m)} �O�@�� reduced residue system modulo m. �h�����N ri $ \in$ S �Ҧs�b�ߤ@�� rj $ \in$ S �ϱo rirj $ \equiv$ 1(mod m).

�� ��. �]�� S �O�@�� reduced residue system modulo m, �C�@�� S �������� si �ҩM m ����, �G�Q�� Proposition 3.2.5 ���s�b b $ \in$ $ \mathbb {Z}$ �ϱo rib $ \equiv$ 1(mod m). �ѩ� b �M m �]�O���誺, �G�� S �O�@�� reduced residue system modulo m ���w�q�����s�b rj $ \in$ S �M b �b modulo m ���U�O�P����, �]�N�O�� b $ \equiv$ rj(mod m). �]���� Lemma 3.1.3 ��, rirj $ \equiv$ rib $ \equiv$ 1(mod m). �ұo�s�b��.

���ߤ@��, �ڭ̥����] rj, rk $ \in$ S �Һ��� rirj $ \equiv$ 1(mod m) �H�� rirk $ \equiv$ 1(mod m). �]���o rirj $ \equiv$ rirk(mod m). ���ѩ� gcd(m, ri) = 1, �Q�� Corollary 3.2.4 �o rj $ \equiv$ rk(mod m). �� S �O reduced residue system modulo m ���� S ���۲��������b modulo m ���U���O���P����, �G�� rj $ \equiv$ rk(mod m) �� rj = rk. �o�Ұߤ@��. $ \qedsymbol$

�Ҧp S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} �O�@�� reduced residue system modulo 11, �b modulo 11 ���U�ڭ̦�

1×1 $\displaystyle \equiv$ 2×6 $\displaystyle \equiv$ 3×4 $\displaystyle \equiv$ 5×9 $\displaystyle \equiv$ 7×8 $\displaystyle \equiv$ 10×10 $\displaystyle \equiv$ 1(mod 11).

�b�o�ӨҤl, S �����F 1 �M 10 �H�~��L�������һݻP�t�~�������ۭ�, �o�b modulo �@�몺��Ƴ��O�諸.

Lemma 3.4.2   ���w�@��� p. �h a $ \in$ $ \mathbb {Z}$ ���� a2 $ \equiv$ 1(mod p) �Y�B�߭Y a $ \equiv$ ±1(mod p).

�� ��. �����Y a $ \equiv$ ±1(mod p), �h a2 $ \equiv$ (±1)2(mod p). �o�� a2 $ \equiv$ 1(mod p).

�Ϥ�, �Y a2 $ \equiv$ 1(mod p), ���� p| a2 - 1, �]�N�O�� p|(a - 1)(a + 1), �G�] p �O���, �Q�� Lemma 1.4.2 �o p| a - 1 �� p| a + 1. �]�N�O�� a $ \equiv$ 1(mod p) �� a $ \equiv$ - 1(mod p). $ \qedsymbol$

�n�`�N Lemma 3.4.2 �b modulo �@�몺�D��Ƥ��U�N���@�w��F, �Ҧp�b modulo 15 ���U���F 1 �M 14 �~, �٦� 4 �|���� 42 $ \equiv$ 1(mod 15), �ӥB����M�� 4 $ \not\equiv$±1 mod15. �ҥH�n�Q�� Lemma 3.4.2, �ڭ̥������w�b��ƪ�����, ���ɧڭ̥i�H�o�� Wilson's Theorem.

Theorem 3.4.3 (Wilson's Theorem)   ���w�@��� p. �] {r1,..., rp - 1} ���@ reduced residue system modulo p. �h

r1 ... rp - 1 $\displaystyle \equiv$ - 1(mod p).

�S�O�a, �ڭ̦�

(p - 1)! $\displaystyle \equiv$ - 1(mod p).

�� ��. �Y p = 2, �h modulo 2 ���U�� reduced residue system �� {r1} �@�Ӥ���, �䤤 r1 $ \equiv$ 1(mod 2). ���b modulo 2 ���U�ڭ̦� 1 $ \equiv$ - 1(mod 2), �G�o�� r1 $ \equiv$ - 1(mod 2).

�{�Ҽ{ p > 2 ������, �O S = {r1,..., rp - 1} �ѩ� gcd(p, 1) = gcd(p, - 1) = 1 �B 1 $ \not\equiv$ - 1(mod p) (�_�h p| 2), �G���O�s�b ri, rj $ \in$ S �䤤 ri$ \ne$rj ���� ri $ \equiv$ 1(mod p) �B rj $ \equiv$ - 1(mod p). �]�����������, �ڭ̥i���] r1 $ \equiv$ 1(mod p) �B r2 $ \equiv$ - 1(mod p). �{�Ҽ{ ri $ \in$ S, �䤤 3$ \le$i$ \le$p - 1. �� Lemma 3.4.1 ���s�b�ߤ@�� rj $ \in$ S �ϱo rirj $ \equiv$ 1(mod p). �]�� ri $ \not\equiv$±1(mod p), �G�� rj $ \not\equiv$±1(mod p), �]�N�O�� 3$ \le$j$ \le$p - 1. �S�Y ri = rj, �|�ɭP ri2 $ \equiv$ 1(mod p), �o�P Lemma 3.4.2 �ۥ٬�, �G�� i$ \ne$j. �]�N�O���b T = {r3,..., rp - 1} �������@���� ri ���i���ߤ@���t�@���� rj $ \in$ T �ϱo rirj $ \equiv$ 1(mod p). �]���ڭ̥i�H�� T ���o p - 3 �Ӥ������t�� (�`�N p �O�_��), �ϱo�C�@�襤�����ۭ��ᰣ�H p �|�l 1. �]�N�O�� r3 ... rp - 1 $ \equiv$ 1(mod p). �]���ڭ̱o��

r1r2r3 ... rp - 1 $\displaystyle \equiv$ r1r2 $\displaystyle \equiv$ - 1(mod p).

�̫�ѩ� {1, 2,..., p - 1} �O�@�� modulo p �� reduced residue system, �G��

1×2× ... ×(p - 1) = (p - 1)! $\displaystyle \equiv$ - 1(mod p).

$ \qedsymbol$

�Y p �O�@��ƥB a �O�M p ���誺���, �ڭ̥i�H�Q�� Wilson's Theorem ���b modulo p ���U, a �����k�Ϥ���. �ѩ�� a $ \equiv$ ±1(mod p) �� a2 $ \equiv$ 1(mod p), �]�N�O�� a �����b modulo p ���U�O�ۤv�����k�Ϥ���, �ҥH�ڭ̶ȰQ�� a $ \not\equiv$±1(mod p) �����p.

Corollary 3.4.4   ���w�@��� p �� a $ \in$ $ \mathbb {Z}$ ���� p$ \nmid$a. ���] a $ \equiv$ i(mod p), �䤤 2$ \le$i$ \le$p - 2. �Y�O

b = $\displaystyle {\frac{(p-2)!}{i}}$

�h ab $ \equiv$ 1(mod p).

�� ��. �ѩ� 2$ \le$i$ \le$p - 2, �ڭ̪� b �O�@�Ӿ��. ����

ab $\displaystyle \equiv$ i$\displaystyle {\frac{(p-2)!}{i}}$ $\displaystyle \equiv$ (p - 2)!(mod p)

�S�ѩ� (p - 1)! = (p - 1) . (p - 2)! �B p - 1 $ \equiv$ - 1(mod p), �G�o��

ab $\displaystyle \equiv$ (p - 2)! $\displaystyle \equiv$ - ((p - 1)!) $\displaystyle \equiv$ 1(mod p).

$ \qedsymbol$

�ڭ̤��n�j�դ@�U���M Lemma 3.4.1 �b�@�몺 m $ \in$ $ \mathbb {N}$ ������, �� Lemma 3.4.2 �ݭ���b��Ʈɤ~����, �ҥH Wilson's Theorem �b modulo �@�몺 m �ä��@�w����. �]�N�O���Y {r1,..., r$\scriptstyle \phi$(m)} �O�@�� reduced residue system modulo m, �ä��@�w�i�H�o r1 ... r$\scriptstyle \phi$(m) $ \equiv$ - 1(mod m). �Ҧp�b modulo 15 ���U�ڭ̤��٦� 4 �M -4 ���� 42 $ \equiv$ (- 4)2 $ \equiv$ 1(mod 15), �ҥH�Q�� Theorem 3.4.3 ���ҩ���k (�Ϊ����p��) �ڭ̥i�o, �Y {r1,..., r8} �O�@�� reduced residue system modulo 15, �h r1 ... r8 $ \equiv$ 1(mod 15). ���M�Q�� Theorem 3.4.3 ����k�ڭ̥i�H�N Wilson's Theorem ���s��@�� m ������, ���L���ɹ�@�� modulo m �� reduced residue system {r1,..., r$\scriptstyle \phi$(m)} ���� ri2 $ \equiv$ 1(mod m) �� ri �|���ܦh�ر���, �Q�װ_�Ӹ�����, �b�o�̧ڭ̴N���h���Q�F.


next up previous
�U�@��: Congruence Equations �W�@��: Congruences �e�@��: Euler's Theorem
Li 2007-06-28