1. a와 b는 서로소 이므로 어떤 자연수 n에 대해서도 a^n 과 b는 서로소이다. a, a^2, a^3, a^4, ..., a^b 들을 b로 나눈 나머지는 1에서 b-1까지의 정수이다. 따라서 비둘기집의 원리에 의해 b로 나눈 나머지가 같은 a^i, a^j가 존재한다. (1<=i,j<=b) 일반성을 잃지 않고 i>j라 하자. b로 나눈 나머지가 같으므로 a^i-a^j 를 b로 나눈 나머지는 0이다 이때 a^i-a^j=a^j(a^(i-j)-1) 에서 a^j는 b와 서로소이므로 (a^(i-j)-1)는 b로 나누어떨어져야 한다. 따라서 a^(i-j)-1은 b로 나누어떨어진다. 그러므로 문제에서 요구하는 양의정수 n은 존재한다.(i-j)
a, a^2, a^3, a^4, ..., a^b 들을 b로 나눈 나머지는 1에서 b-1까지의 정수이다.
따라서 비둘기집의 원리에 의해 b로 나눈 나머지가 같은 a^i, a^j가 존재한다. (1<=i,j<=b)
일반성을 잃지 않고 i>j라 하자.
b로 나눈 나머지가 같으므로 a^i-a^j 를 b로 나눈 나머지는 0이다
이때 a^i-a^j=a^j(a^(i-j)-1) 에서 a^j는 b와 서로소이므로 (a^(i-j)-1)는 b로 나누어떨어져야 한다.
따라서 a^(i-j)-1은 b로 나누어떨어진다.
그러므로 문제에서 요구하는 양의정수 n은 존재한다.(i-j)