1514C - Product 1 Modulo N

 1514C - Product 1 Modulo N

Link : https://codeforces.com/problemset/problem/1514/C

Problem statement

We are given a number $n$, for which we want to find the maximum count of numbers which are less than this $n$, and have the modulo of their product as 1.

Solution

Here, the crux of the solution is this math stack exchange's post : https://math.stackexchange.com/questions/441667 

The critical point being:

Let $1 \leq b_1 < b_2 <...< b_{\phi(n)} < n$ be integers relatively prime with n.Prove that 

$$B_n = b_1 b_2 ... b_{\phi(n)} \equiv \pm 1 \bmod n $$

This can be proven by seeing that there are two types of numbers amongst Bs. One, which have a partner number, such that their product is 1 modulo $n$.

Two, which don't have a partner, and their product to themselves (i.e their square) modulo $n$ is $1$. But we don't have two of them. Instead note that $$ (x \times (n - x) ) \text{%} n = (-x^2)\text{%} n = -1$$

So let's see what the product of these two types of numbers will be. The first one will only contribute to 1, but the 2nd ones will contribute -1 for each of them. 

So we just have to multiply the co-primes, and check whether their product modulo $n$ is 1. If not, it will be $n-1$. This means that we can remove the pair of the 2nd type $1, (n-1)$ from the co-primes list. This would decrease the pairs of the 2nd type by 1, and thus our product will become 1 again. 

Note that removing 1 wouldn't make any sense from the co-primes, so we can just remove $n-1$. 

My submission : https://codeforces.com/contest/1514/submission/181683452