오일러 토션트 함수

(오일러의 totient 함수에서 넘어옴)
둘러보기로 가기 검색하러 가기

정의

• 1부터 n까지의 양의 정수 중에 n과 서로소인 수의 개수를 나타내는 함수
• $$\varphi(n)$$ 으로 나타냄

성질

• 서로 소인 자연수 $$m,n$$ 에 대하여, $$\varphi(mn)=\varphi(m)\varphi(n)$$
• 소수 $$p$$ 에 대하여, $$\varphi(p^{k}) = (p - 1)p^{k - 1}$$
• $$\varphi (1) = 1$$
• 일반적으로, 2 이상의 자연수 n의 소인수분해가 $$n=p_1 ^{\alpha _1} p_2 ^{\alpha _2} ... p_k ^{\alpha _k}$$ 으로 주어지면, $$\varphi (n) = p_1 ^{\alpha _1 - 1} p_2 ^{\alpha _2 - 1} ... p_k ^{\alpha _k - 1} (p_1 - 1)(p_2 - 1) .. (p_k - 1)$$ 이 된다.

합동식에의 응용

• 1부터 n까지의 양의 정수 중에 n과 서로소인 수로 구성된 집합은 곱셈 (mod n) 에 대한 군의 구조를 이룸
• 이 군을 $$(\mathbb{Z}/n\mathbb{Z})^\times$$ 로 표현하며, 원소의 개수는 $$\varphi(n)$$ 이 됨.

원분체

• 원분체 (cyclotomic field) $$K = \mathbb Q(\zeta_n)$$
• $$[\mathbb Q(\zeta_n): \mathbb Q)] = \varphi(n)$$
• 갈루아군은 $$\text{Gal}(\mathbb Q(\zeta_n) /\mathbb Q) \simeq (\mathbb{Z}/n\mathbb{Z})^\times$$를 만족하며, 그 크기는 $$\varphi(n)$$ 이 됨.

100까지의 자연수에 대한 totient 함수값 목록

$$n$$ $$\varphi(n)$$

1 1 2 1 3 2 4 2 5 4 6 2 7 6 8 4 9 6 10 4 11 10 12 4 13 12 14 6 15 8 16 8 17 16 18 6 19 18 20 8 21 12 22 10 23 22 24 8 25 20 26 12 27 18 28 12 29 28 30 8 31 30 32 16 33 20 34 16 35 24 36 12 37 36 38 18 39 24 40 16 41 40 42 12 43 42 44 20 45 24 46 22 47 46 48 16 49 42 50 20 51 32 52 24 53 52 54 18 55 40 56 24 57 36 58 28 59 58 60 16 61 60 62 30 63 36 64 32 65 48 66 20 67 66 68 32 69 44 70 24 71 70 72 24 73 72 74 36 75 40 76 36 77 60 78 24 79 78 80 32 81 54 82 40 83 82 84 24 85 64 86 42 87 56 88 40 89 88 90 24 91 72 92 44 93 60 94 46 95 72 96 32 97 96 98 42 99 60 100 40

메타데이터

Spacy 패턴 목록

• [{'LOWER': 'euler'}, {'LOWER': "'s"}, {'LOWER': 'totient'}, {'LEMMA': 'function'}]
• [{'LOWER': 'phi'}, {'LEMMA': 'Function'}]