모든 소수 p에 대해 (p-1)! = p-1 (mod p)인가?p = 2에서 증명1 = 1 (mod 2) 이므로 참p = 3에서 증명2 = 2 (mod 3) 이므로 참p > 3에서 증명선형합동방정식의 정리에 의해 ax ≡ b (mod m), gcd(a, m) = 1일때유일한 해를 가진다. (x=bu/g, au+mv=1)(p-1)! (mod p)에서도 p-1, p-2, ... 1은 모두 p와 서로소 관계이다.따라서 aa' ≡ 1 (mod p)인 a'도 0~p-1 범위 내에 유일하게 가진다.이때 특수한 경우인 x^2 ≡ 1 (mod p)를 만족하는 x = 1, p-1 말고 나머지는 2~p-2가 짝수개이므로서로 짝지을 수 있다.a ≡ b (mod m1), a ≡ b (mod m2)⇒ a1a2 ≡ b1b2 (m..

// 중간에 순서를 바꾸는 경우를 위해 swap 함수를 정의해놨다.void swap(int[] arr, int i, int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;} 버블 정렬 (bubble sort)옆에 있는 것과 비교하며 계속 이동예) 4 3 2 1 를 정렬한다면    round 1: 3 2 1 4    round 2: 2 1 3 4    round 3: 1 2 3 4-> 정렬 라운드마다 맨 끝의 수가 정렬된다.void bubble_sort(int[] arr){ for (int i = 0; iarr[j+1]) swap(arr, j, j+1) } }}2중 중첩 반복문에 각 반복문마다 ..