자연수 $n$에 대하여 $n$과 서로 소인 $n$ 이하의 자연수의 개수를 $\phi(n)$, $n$의 소인수의 개수를 $\phi(n)$이라고 하자. $\phi(n)$이 $n-1$의 약수이고 $\phi(n)\le 3$이면 $n$이 소수임을 증명하라.
태그 보관물: 소수
2002 제15회 한국수학올림피아드 최종시험 6번문제
소수를 작은 것부터 차례로 $p_1=2$, $p_2=3$, $p_3=5$, $\ldots$라 하자.
(1) 주어진 자연수 $n\ge 10$에 대하여, $r$을 $2\le r\le n-2$와 $n-r+1\lt p_r$을 동시에 만족시키는 최소의 정수라 하자. 모든 $s=1,2,\ldots,p_r$에 대하여 $N_s=(sp_1p_2\cdots p_{r-1})-1$로 정의할 때, $p_1$, $p_2$, $\ldots$, $p_n$ 중 어떤 수도 약수로 가지지 않는 $N_j$가 존재함을 보여라. 단, $1\le j\le p_r$.
(2) (1)의 결과를 써서 부등식 $p_{m+1}^2\lt p_1p_2\cdots p_m$을 만족시키는 자연수 $m$을 모두 구하여라.
2013 국제대학생수학경시대회(IMC) 첫째날 5번문제
모든 양의 정수 $p$에 대해 $\sum_{n=1}^\infty a_n^p$가 수렴할 필요충분조건이 $p$가 소수인 것이 되도록 하는 복소수의 수열 $(a_n)$이 존재하는가?
(2013년 8월 8일, 불가리아, 5문제, 출처)
2012 국제수학올림피아드 Short List A4
항등적으로 $0$인 다항식이 아닌 두 정수 계수 다항식 $f(x)$, $g(x)$에서 $f$의 차수가 $g$의 차수보다 크다고 한다. 식 $pf(x)+g(x)=0$에 유리수해가 존재하게 하는 소수 $p$가 무한히 많다고 할 때 $f(x)=0$ 역시 유리수해를 가진다는 것을 증명하라.
2013 루마니아 TST2 3번문제
어떤 양의 정수 $n, a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n$을 이용하여 \[\frac{(a_1^2+a_1-1)(a_2^2+a_2-1)\cdots (a_n^2+a_n-1)}{b_1^2+b_1-1)(b_2^2+b_2-1)\cdots (b_n^2+b_n-1)}\] 꼴로 나타낼 수 있는 모든 유리수의 집합을 $S$라 하자. 이때 집합 $S$ 안에 소수가 무한이 많음을 보여라.
(출처)
2013 제5회 베네룩스수학올림피아드 4번문제
a) 다음 성질을 만족하는 모든 양의 정수 $g$를 구하여라: 임의의 홀수인 소수 $p$에 대해 다음 두 수 \[ g^n-n\text{와 }g^{n+1}-(n+1)\]이 모두 $p$의 배수가 되는 양의 정수 $n$이 존재한다.
b) 다음 성질을 만족하는 모든 양의 정수 $g$를 구하여라: 임의의 홀수인 소수 $p$에 대해 다음 두 수 \[ g^n-n^2\text{와 }g^{n+1}-(n+1)^2\]이 모두 $p$의 배수가 되는 양의 정수 $n$이 존재한다.
(2013년 4월 27일, 4시간 30분, 네덜란드 도르드레흐트, 출처)