2017년 8월 11일 (금) 02:47에 Admin님의 편집

2017-08-11T02:47:39Z

Admin: 새 문서: When $a$ and $n$ are coprime positive integers, then $$ a ^{\varphi(n)} \equiv 1 \quad (\text{mod}\ n) $$ where $\varphi (n)$ is [https://en.wikipedia.org/wiki/Euler%27s_totient...

2017-08-10T07:22:53Z

새 문서: When $a$ and $n$ are coprime positive integers, then $$ a ^{\varphi(n)} \equiv 1 \quad (\text{mod}\ n) $$ where $\varphi (n)$ is [https://en.wikipedia.org/wiki/Euler%27s_totient...

새 문서

When $a$ and $n$ are coprime positive integers, then
$$ a ^{\varphi(n)} \equiv 1 \quad (\text{mod}\ n) $$
where $\varphi (n)$ is [https://en.wikipedia.org/wiki/Euler%27s_totient_function Euler’s totient function]. 즉, $n$보다 작으면서 $n$과 서로소인 자연수의 갯수. 예를들어, $\varphi(10) = 4 ( \{1, 3, 7, 9\})$. $n$이 prime이면 $\varphi(n) = n-1$.

$\mathbf{R}=${$x_1, x_2, \cdots, x_{\phi(n)}$}을 [https://en.wikipedia.org/wiki/Reduced_residue_system reduced residue system] (mod $n$)이라고 하면, $n$과 coprime인 임의의 수 $a$를 곱했을 때, 다시 (순서만 뒤섞인) $\mathbf{R}$이 된다. 즉, {$x_1, x_2, \cdots, x_{\phi(n)}$} = {$ax_1, ax_2, \cdots, ax_{\phi(n)}$}. 왜냐하면 $ax_j \equiv ax_k$ (mod $n$)이면 $j = k$이어야 하기 때문이다.<ref>Refer to [https://en.wikipedia.org/wiki/Modular_arithmetic#Properties modular arithmetic]. Compatibility with scaling.</ref>

따라서
$$\prod_{i=1}^{\varphi(n)} x_i \equiv
\prod_{i=1}^{\varphi(n)} ax_i \equiv
a^{\varphi(n)}\prod_{i=1}^{\varphi(n)} x_i \pmod{n}$$
이고, 양변 cancel하면 $
a^{\varphi(n)}\equiv 1 \pmod{n}
. \ \square$

← 이전 판		2017년 8월 11일 (금) 02:47 판
12번째 줄:		12번째 줄:
	a^{\varphi(n)}\equiv 1 \pmod{n}		a^{\varphi(n)}\equiv 1 \pmod{n}
	. \ \square\)		. \ \square\)
		+
		+	위키에 보면 직관적이지 않아서 외워두지 않으면 쉽게 추론하기 힘든 것들[https://en.wikipedia.org/wiki/Euler%27s_totient_function#Other_formulae]이 보인다. 심심풀이로 봐두면 좋을듯.

Euler's theorem - 편집 역사

2017년 8월 11일 (금) 02:47에 Admin님의 편집

Admin: 새 문서: When \(a\) and \(n\) are coprime positive integers, then $$ a ^{\varphi(n)} \equiv 1 \quad (\text{mod}\ n) $$ where \(\varphi (n)\) is [https://en.wikipedia.org/wiki/Euler%27s_totient...