위 문제에서 구하고자 하는 것은 다음과 같다. $$\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$가 서로소가 아니므..

이전에 조합을 소수의 $k$제곱으로 나눈 나머지를 구하는 방법을 소개했다. 그 방법은 너무 어렵기 때문에 조금 더 쉬운 방법을 소개한다. - Notation $(u!)_{p}$는 $u!$에서 $p$의 배수인 것을 제외한 곱을 의미한다. 소수 $p$와 자연수 $k$에 대하여 $p^{2k}$으로 나눈 나머지를 구한다고 하자. 이때 다음 식을 이용한다. $$\frac{(dp^{k}!)_{p}}{((d-1)p^{k}!)_{p}} \equiv (p^{k}!)_{p} \pmod{p^{2k}}$$ 풀어서 써보면 다음과 같다. $p^{k}$와 서로소인 $p^{k}$이하의 자연수들의 집합을 $\{S\}$라고 하자. \[\prod_{a \in S} (dp^{k}+a) \equiv \prod_{a \in S} a \pmod..

$$f(n) = \sum_{d|n} g(d)$$ 이라고 하자. 이때 $g(n)$의 값을 구하고 싶다. 이때 적용되는 식이 뫼비우스 역공식이다. $$g(n)= \sum_{d|n} f(d)\mu(\frac{n}{d})$$ $f$가 곱셈적 함수이고 $f(n) = \sum_{d|n} g(d)$이면 $g$ 역시 곱셈적 함수이다. Notation $[P=k]$ : $P=k$일 때 1 아니면 0 $\epsilon(n)$ : $[n=1]$ $\sum_{d|n} \mu(d) =\epsilon(n)$ $\tau(n)$ : $n$의 약수의 개수 $a \perp b$은 $\gcd(a,b)=1$라는 뜻 $$1.\ \ \sum_{i=1}^{n} \sum_{j=1}^{m} \gcd(i, j)$$ \[\sum_{d=1}^{\min(..

이 문제의 목표는 모든 자연수 $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^..

플래티넘 새싹을 얻었다!

보호되어 있는 글입니다.