수학/정수론

• 오일러 피 함수(Euler's phi function)

  수학/정수론 2024. 1. 24. 11:54

  정의1서로소 판별함수 :임의의 양의 정수 $m, n \in \mathbb{Z}^+$에 대해 $\mathbf{1}_n(m) = \begin{cases} 1 ,&  \gcd(m,n) = 1 \text{일때} \\ 0 ,&  \gcd(m,n) \ne 1 \text{일때}  \end{cases}$ 로 정의되는  산술함수 $\mathbf{1}_n : \mathbb{Z}^+ \to \{ 0, 1 \}$를 $n$에 대한 서로소 판별함수로 정의한다.오일러 피 함수 : 모든 $n \in \mathbb{Z}^+$에 대해 $\phi(n) = \displaystyle \sum_{ m = 1}^n \mathbf{1}_n(m)$ 으로 $n$과 서로소인 $n$보다 작거나 같은 양의 정수의 개수를 세는 산술함수 $\phi : \ma..

• 산술 함수(Arithmetic function)

  수학/정수론 2023. 9. 10. 12:31

  정의1약수 집합 : 임의의 양의 정수 $n \in \mathbb{Z}^+$에 대해$n / d \in \mathbb{Z}$인 모든 양의 정수 $d \in \mathbb{Z}^+$들의 집합 $D_n = \{ d \in \mathbb{Z}^+ :  n/d \in \mathbb{Z}  \}$을 $n$의 약수집합으로 정의한다.약수의 개수 $\tau$-함수 :$D_n$의 원소개수가 $m_n \in \mathbb{Z}^+$개일때 $n$을 나누는 모든 양의 정수들의 개수를$\displaystyle \tau(n) = m_n $인 함수 $\tau : \mathbb{Z}^+ \to \mathbb{Z}^+$로 정의한다.약수의 합 $\sigma$-함수 :$D_n = \{ d_{1,n}, d_{2,n}, \cdots, d_{\t..

• 소수(Prime number)

  수학/정수론 2023. 8. 31. 17:03

  정의1임의의 양의 정수 $n \in \mathbb{Z}^+$에 대해$p / n \in \mathbb{Z}$이면 $n = 1$ 또는 $n = p$가 되는 $p \ge 2$인 양의 정수 $p \in \mathbb{Z}^+$를 소수로 정의한다.소수가 아니고 $1$보다 큰 양의 정수를 합성수(composite number)로 정의한다.   정리1$p \in \mathbb{Z}^+$가 소수일때 임의의 정수 $a, b \in \mathbb{Z}$에 대해 $(a\cdot b) / p \in \mathbb{Z}$이면 $a / p \in \mathbb{Z}$이거나 $b / p \in \mathbb{Z}$이다.증명$(a\cdot b) / p \in \mathbb{Z}$일때 $a / p \notin \mathbb{Z}$이고..

• 모듈로 합동(Congruent Modulo)

  수학/정수론 2023. 7. 31. 19:17

  정의1임의의 정수 $a,b \in \mathbb{Z}$가 임의의 양의 정수 $n \in \mathbb{Z}^+$에 대해  $(a - b)/n \in \mathbb{Z}$으로 $a-b = q\cdot n$이 되는 정수 $q \in \mathbb{Z}$가 존재할때$a$와 $b$가 $n$에 대해 모듈로 합동(congruent modulo n)이라 하고 $a \equiv b \pmod{ n}$로 표기한다.$(a - b)/n \notin \mathbb{Z}$이면 $a$와 $b$가 $n$에 대해 모듈로 합동이 아니라 하고 $a \not \equiv b \pmod{ n}$로 표기한다. 나눗셈 정리로 $a = q\cdot n + r$이고 $0\le r $\bmod n = \{ (a,r) \in \mathbb{Z} \t..

• 약수(Divisor), 배수(Multiple)

  수학/정수론 2023. 7. 28. 13:32

  정리1(나눗셈 정리)임의의 정수 $a,b \in \mathbb{Z}$에 대해 다음이 성립한다.1. $a >0$이면 $0 \le r 2. $a $a증명1.$a > 0$일때 $q,r \in \mathbb{Z}$의 존재성을 보인다.집합 $S = \{ b - x\cdot a : x \in \mathbb{Z} \text{ 이고 } b - x\cdot a \ge 0 \} \subseteq \mathbb{Z}$를 정의할때자연수 부등식 정리로 $a \ge 1$이고 절댓값 정리로 $|b| \ge 0$에 대해 부등식 정리로 $|b|\cdot a \ge |b| \cdot 1 = |b|$와 $b - (-|b|)\cdot a = b + |b|\cdot a \ge b + |b| $가 성립하여절댓값 정리로 $b \ge -|b..

• 이항계수(Binomial coefficient)

  수학/정수론 2023. 5. 26. 17:46

  정의1임의의 양의 정수 $n \in \mathbb{Z}^+$에 대해 $n ! = 1\cdot 2 \cdot 3 \cdots (n-1)\cdot n$인$1$에서 $n$까지의 곱을 $n$의 계승 또는 팩토리얼(factorial)이라 정의한다.$0$의 팩토리얼은 $0! = 1$로 정의된다.   정의2$n \ge  k \ge 0 $인 모든 자연수 $n,k \in \mathbb{N}$에 대해 $  \dbinom{n}{k} = \dfrac{n!}{k!(n-k)!}$를 이항 계수로 정의한다.   정리1(파스칼[Pascal] 항등식)$n \ge  k \ge 1$인 모든 양의 정수 $n,k \in \mathbb{Z}^+$에 대해 $\dbinom{n+1}{k} = \dbinom{n}{k-1}+\dbinom{n}{k}$이다..