Let us consider two disjoint cases:
- N is a composite number. In this case, we wish to use the factorization of N:
- If N can be written as a product of two different integers (N = A × B, 1 < A < B < N), it means that both A and B appear in the product 1 × 2 × … × (N-1). Therefore, N divides the product.
- If N cannot be written as a product of two different integers, it means that N can be written as a product of two identical integers (remember that N is a composite number). Each of the two numbers is equal to sqrt(N).
Because 1 < sqrt(N) < 2×sqrt(N) < N for any N greater than 4[1], both square roots will appear somewhere in the product 1 × 2 × … × (N-1). Therefore, sqrt(N) × sqrt(N) = N divides the product.
[1]: N = 4 is a particular case and should be dealt with independently.
- N is a prime number. In this case, we make use of Lagrange's Theorem, which states that the residue classes (mod N) are a field. This means that every non-zero integer a has a unique multiplicative inverse a-1.
- For the most part, a ≠ a-1. These means that we can match elements in pairs such that each pair has a product congruent to 1 (mod N).
- However, there might be some elements a for which a ≡ a-1 (mod N). This is equivalent to a2 ≡ 1 (mod N). Because a polynomial of degree 2 has at most 2 roots in any field (again, Lagrange), we can be sure that the only values of a for which the previous equation holds are ±1. This means that ±1 (or 1 and N-1, if you wish) are their own multiplicative inverses. As a consequence, we cannot pair 1 with itself, and we cannot pair N-1 with itself. However, we can pair 1 with N-1, and get a multiplicative residue of N-1.
Now we have (N-3)/2 pairs with products congruent to 1, and exacty one pair with the product congruent to N-1. The following expression will hold: 1 × 2 × … × (N-1) ≡ N-1 (mod N). Therefore, the answer in this case is N-1.
You can find more info on Wikipedia's article on Wilson's theorem.
The problem is reduced to determining whether or not N is a prime number. This can be solved in O(sqrt(N)) time complexity.
Python solution (Sergiu Puscas)
1 import math
2 n = input()
3
4 print 2 if n == 4 else (0 if any(n % x == 0 for x in range(2, int(math.sqrt(n))+1)) else n-1)
Ruby solution (Croitoru Radu Bogdan)
1 require 'prime'
2
3 n = gets.chomp.to_i
4 puts n==4? 2:(Prime.prime?(n)? n-1:0)
C++ solution (Gabriel Inelus)
1 #include <iostream>
2 int N, p;
3 int main() {
4 std::cin >> N;
5 for(int i = 2; i * i <= N && !p; ++i)
6 p |= (N % i == 0);
7
8 if(N == 4) std::cout << 2;
9 else if(p) std::cout << 0;
10 else std::cout << N - 1;
11
12 return 0;
13 }
