오일러의 토션트 함수

Core idea

Overview

오일러의 토션트 함수는 주요 입력값과 식의 관계를 정리하고 계산 결과의 의미를 해석하기 위한 설명입니다. 조건, 단위, 전제를 확인하면서 사용하면 결과를 비교, 판단, 추정, 위험 확인과 연결하기 쉽습니다. 필요하면 값을 바꾸어 결과가 어떻게 달라지는지도 확인하세요.

When to use: 오일러의 토션트 함수는 주어진 값에서 필요한 결과를 구해야 할 때 사용합니다. 입력 단위, 범위, 전제 조건을 확인한 뒤 대입하고, 계산 결과를 실제 조건이나 문제의 목적과 비교해 해석하세요.

Why it matters: 오일러의 토션트 함수의 결과는 수치를 비교하고 경향, 제약, 위험, 설계 판단을 설명하는 데 도움이 됩니다. 답을 단독 숫자로만 보지 말고 조건이 바뀔 때의 의미와 타당성도 함께 확인할 수 있습니다.

Symbols

Variables

$ϕ$ (n) = Totient Value, n = Input Integer

ϕ (n)

Totient Value

Variable

n

Input Integer

Variable

Walkthrough

Derivation

오일러의 토션트 함수 유도/이해

이 유도는 주어진 정수 n까지의 양의 정수 중 n과 서로소인 것의 개수를 세는 오일러의 토션트 함수가 n의 소인수분해를 사용하여 표현될 수 있음을 보여줍니다.

1

정의와 곱셈적 성질:

우리는 오일러의 토션트 함수를 정의하고 그 중요한 곱셈적 성질을 진술하는 것으로 시작합니다. 이 성질은 합성수에 대한 계산을 그들의 소수 거듭제곱 인자에 대한 계산으로 분해할 수 있게 해줍니다.

Euler’s totient function ϕ (n) counts the positive integers up to n that are relatively prime to n . It is a multiplicative function, meaning if g cd (m, n) = 1, then ϕ (mn) = ϕ (m) ϕ (n) .

2

소수 거듭제곱의 경우:

$p^{k}$ 소수 거듭제곱에 대해, 그것과 서로소가 아닌 유일한 숫자는 $p$ 의 배수들입니다. 전체 $p^{k}$ 개의 숫자에서 이들을 빼면 $ϕ (p^{k})$ 에 대한 공식을 얻습니다.

Consider n = p^{k} for a prime p and integer k \geq 1. The integers not relatively prime to p^{k} are multiples of p : p, 2 p, \dots, p^{k - 1} p . There are p^{k - 1} such multiples up to p^{k} . ϕ (p^{k}) = p^{k} - p^{k - 1} = p^{k} (1 - \frac{1}{p}) .

3

소인수분해를 사용한 일반적인 경우:

산술의 기본 정리를 사용하면, 모든 양의 정수 $n$ 는 소수 거듭제곱의 곱으로 유일하게 표현될 수 있습니다. $ϕ (n)$ 의 곱셈적 성질은 우리가 각 인자에 소수 거듭제곱 공식을 적용할 수 있게 해줍니다.

Let the prime factorization of n be n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}} . Due to the multiplicative property, we can write: ϕ (n) = ϕ (p_{1}^{k_{1}}) ϕ (p_{2}^{k_{2}}) \dots ϕ (p_{r}^{k_{r}}) .

4

대입 및 단순화:

각 소수 거듭제곱 인자에 대해 유도된 $ϕ (p^{k})$ 공식을 대입하고 항을 재배열함으로써, 우리는 오일러의 토션트 함수에 대한 곱 공식에 도달합니다. 여기서 곱은 $n$ 의 모든 서로 다른 소인수 $p$ 에 대해 취해집니다.

Substitute the formula for ϕ (p^{k}) into the expression: ϕ (n) = p_{1}^{k_{1}} (1 - \frac{1}{p _{1}}) \cdot p_{2}^{k_{2}} (1 - \frac{1}{p _{2}}) \dots p_{r}^{k_{r}} (1 - \frac{1}{p _{r}}) ϕ (n) = (p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}) (1 - \frac{1}{p _{1}}) (1 - \frac{1}{p _{2}}) \dots (1 - \frac{1}{p _{r}}) Recognizing that n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}, we get: ϕ (n) = n p ∣ n \prod (1 - \frac{1}{p}) .

Result

Substitute the formula for ϕ (p^{k}) into the expression: ϕ (n) = p_{1}^{k_{1}} (1 - \frac{1}{p _{1}}) \cdot p_{2}^{k_{2}} (1 - \frac{1}{p _{2}}) \dots p_{r}^{k_{r}} (1 - \frac{1}{p _{r}}) ϕ (n) = (p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}) (1 - \frac{1}{p _{1}}) (1 - \frac{1}{p _{2}}) \dots (1 - \frac{1}{p _{r}}) Recognizing that n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}, we get: ϕ (n) = n p ∣ n \prod (1 - \frac{1}{p}) .

Source: Rosen, K. H. (2011). Elementary Number Theory and Its Applications (6th ed.). Pearson.

Why it behaves this way

Intuition

1부터 n까지의 모든 숫자로 시작하여 n의 각 서로 다른 소인수의 모든 배수를 체계적으로 걸러내어 n과 공통 인자가 없는 숫자만 남기는 체(sieve)를 상상해보세요.

ϕ (n)

n 이하의 양의 정수 중 n과 서로소인 것의 개수.

n까지의 숫자의 '서로소 밀도' 또는 '상대적 소수성'을 나타냅니다. 더 큰

ϕ

(n)은 n과 공통 소인수를 공유하지 않는 숫자가 더 많다는 것을 의미합니다.

n

토션트가 계산되는 양의 정수.

고려되는 정수 범위의 상한; 1부터 n까지의 숫자의 '우주'.

p

n의 서로 다른 소인수.

이것들은 n의 기본적인 소수 구성 요소이며, 공유되면 다른 숫자들이 n과 서로소가 되는 것을 방지합니다.

(1 - \frac{1}{p})

p로 나누어 떨어지지 않는 n 이하의 숫자들의 비율.

이 인자는 n과 소인수 p를 공유하는 숫자들을 '제거'하여, p를 기준으로 서로소가 아닌 숫자들을 효과적으로 걸러냅니다.

Signs and relationships

(1 - \frac{1}{p}): 뺄셈 '1 - ...'은 배제 원리를 나타냅니다. 전체 집합(1로 표시)에서 소인수 p로 나누어 떨어지는 숫자의 비율(1/p)을 뺍니다.

Free study cues

Insight

Canonical usage

오일러 피 함수는 정수 개수를 입력으로 받아 정수 개수를 반환하며, 이는 물리적 의미에서 본질적으로 무차원량입니다.

Dimension note

이 함수는 정수의 개수를 계산하므로 입력과 출력 모두 본질적으로 무차원량입니다. 물리적 단위나 차원을 포함하지 않습니다.

One free problem

Practice Problem

다음 조건을 사용해 오일러의 토션트 함수을(를) 구하세요. 필요한 값을 식에 대입하고 단위와 자릿수를 확인해 답하세요. 조건: 12, 12, 1.

Hint: 오일러의 토션트 함수의 식에 알려진 값을 대입하고 단위, 부호, 분자와 분모의 대응을 확인하면서 계산하세요. 문제에서 주어진 조건을 먼저 정리하면 더 쉽게 풀 수 있습니다.

The full worked solution stays in the interactive walkthrough.

Where it shows up

Real-World Context

오일러의 토션트 함수는 실무, 학습, 분석 상황에서 구체적인 값을 대입해 결과를 확인할 때 사용할 수 있습니다. 계산 결과를 단순한 숫자로만 보지 않고 조건 비교, 판단, 추정, 위험 확인과 연결해 해석하는 데 도움이 됩니다. 관련 기호: \phi.

Study smarter

Tips

n이 소수이면 φ(n) = n - 1입니다.
서로 다른 소인수만 식별하세요. 인수분해에서 같은 인수가 여러 번 나타나도 반복해서 세지 마세요.
소수 거듭제곱 pᵏ의 경우 값은 pᵏ - pᵏ⁻¹입니다.
이 함수는 곱셈적입니다. m과 n이 서로소이면 φ(m ×n) = φ(m) ×φ(n)입니다.

Avoid these traps

Common Mistakes

곱셈 공식에서 고유한 소인수만 포함해야 하는데 모든 약수를 잘못 포함합니다.
phi(n)을 약수의 개수 $τ$ (n)와 혼동합니다.

Keep going

Related Formulas

Common questions

Frequently Asked Questions

이 유도는 주어진 정수 n까지의 양의 정수 중 n과 서로소인 것의 개수를 세는 오일러의 토션트 함수가 n의 소인수분해를 사용하여 표현될 수 있음을 보여줍니다.

오일러의 토션트 함수는 주어진 값에서 필요한 결과를 구해야 할 때 사용합니다. 입력 단위, 범위, 전제 조건을 확인한 뒤 대입하고, 계산 결과를 실제 조건이나 문제의 목적과 비교해 해석하세요.

오일러의 토션트 함수의 결과는 수치를 비교하고 경향, 제약, 위험, 설계 판단을 설명하는 데 도움이 됩니다. 답을 단독 숫자로만 보지 말고 조건이 바뀔 때의 의미와 타당성도 함께 확인할 수 있습니다.

곱셈 공식에서 고유한 소인수만 포함해야 하는데 모든 약수를 잘못 포함합니다. phi(n)을 약수의 개수 \tau(n)와 혼동합니다.