어떤 홀수가 주어질 때 그 홀수를 세 개의 소수의 합으로 나타내는 방법이 얼마나 많은지 구하는 문제이다. 주어진 홀수를 $n$이라 하자. 그럼 경우는 3가지가 있다. 각 경우마다의 경우의 수를 $a, b, c$라고 두자. 1. $n=p+q+r$ 2. $n=2p+q$ 3. $n=3p$ 가장 쉽게 생각할 수 있는 것은 소수 차의 항만을 가지며 계수가 1인 다항식 $P(x)$를 생각할 수 있다. 이 $P(x)^{3}$에서 $x^n$의 계수가 우리가 구하고자 하는 답과 가장 유사할 것이다. 하지만 그 계수는 $6a+3b+c$가 된다. $c$는 쉽게 구할 수 있으나 $b$를 구하는 것이 어렵다. $b$는 $P(x)$에서 각 항의 차수만 2배가 된 식 $Q(x)$와 $P(x)$를 곱하게 된다면 $x^n$의 계수로 ..

함수 $f$는 다음과 같이 정의된다. $$f(a)=a^{N} \pmod{N}$$ $$F_{1}(a)=f(a)$$ $$F_{k+1}(a)=F_{k}(f(a)) (k=1,2,3,...)$$ 이를 간단히 하면 다음과 같다. $$F_{k}(a)=a^{N^{k}} \pmod{N}$$ 이때 $F_{k}(a)=a$인 최소의 $k$를 찾는 것이 우리의 목표이다. 먼저 $N=p$(소수)일 경우를 생각해보자. $$a^{N^{k}} \equiv a \pmod{N}$$ 이때 $gcd(a,N)=1$이므로 $$a^{N^{k}-1} \equiv 1 \pmod{N}$$ $$N^{k} \equiv 1 \pmod{\phi(N)}$$ 만약 이때 $\gcd(N,\phi(N))=1$이 아니라면 만족하는 $k$가 존재하지 않는다. $k$가 존..

위 문제에서 구하고자 하는 것은 다음과 같다. $$\sum_{i=1}^{a} \sum_{j=1}^{b} \sum_{k=1}^{c} \tau(ijk)$$ 필요한 이론을 증명하고 문제를 해결하자. Theorm 1. $$\tau(ij)=\sum_{x|i} \sum_{y|j} [x \perp y]$$ Lemma 1. $$n=\prod_{i=0}^{k} p_{i}^{a_{i}}t\ \ (p_{i} \nmid t)$$ 일 때 다음은 $n$의 약수 중 $p_{i}$들의 배수의 개수이다. $$\prod_{i=0}^{k} a_{i} \tau(t)$$ $i=p^{a}s(p \nmid s),\ j=p^{b}t(p \nmid t)$라 가정하자. $$\tau(ij)=(a+b+1)\tau(st)$$ $s, t$가 서로소가 아니므..

이 문제의 목표는 모든 자연수 $a$에 대해서 $(a+d)^{k}-a^{k}$를 나누는 가장 큰 자연수($N$)를 구하는 것입니다. $N$은 $d$의 소인수들의 구성으로만 이루어져 있다. 어떤 소수 $p$가 존재하고 $p |N$이라고 합시다. 그럼 다음을 만족합니다. $$(a+d)^{k} \equiv a^{k} \pmod{p}$$ $$d \equiv 0 \pmod{p}$$ 따라서 $p$는 $d$의 소인수입니다. $p$가 $d$의 소인수인 것은 알았지만 $(a+d)^{k}-a^{k}$이 몇 번 $p$로 나누어 떨어지는 지는 아직 모릅니다. 이 문제를 해결하기 위해서 Lifting-the-exponent lemma를 사용하였습니다. Lifting-the-exponent lemma $v_{p}(n)$는 $p^..

플래티넘 새싹을 얻었다!

페리 수열 $F_{n}$은 0부터 1까지 분모가 $n$이하인 모든 기약분수들을 오름차순으로 배열한 수열이다. 예를 들어 $n=3$ 이라면 수열은 다음과 같다. $\frac{0}{1}\ \frac{1}{3}\ \frac{1}{2}\ \frac{2}{3}\ \frac{1}{1}$ 페리 수열은 이전 수열에 새로운 기약분수가 추가되며 수열이 만들어진다. 페리 수열의 $a$번째 항을 $\frac{h_1}{k_1}$, $a+2$번째 항을 $\frac{h_2}{k_2}$, $a+1$번째 항을 $\frac{h_3}{k_3}$이라 하면 $h_{3}=h_{1}+h_{2}$, $k_{3}=k_{1}+k_{2}$ 이다. 이 성질을 이용해 이 다음 페리 수열에 등장할 분수를 알 수 있다. 페리 수열의 크기를 $|F_{n}|$이..