IMO Shortlist 2004 N6

Discussion on International Mathematical Olympiad (IMO)
mutasimmim
Posts:107
Joined:Sun Dec 12, 2010 10:46 am
IMO Shortlist 2004 N6

Unread post by mutasimmim » Wed Dec 24, 2014 7:52 pm

For a natural number $n$, let $P_{n}$ denote the product of the natural numbers $x<n$ such that $n\mid (x^2-1).$. Find $P_{n} (mod n)$ in terms of $n$.

User avatar
Fm Jakaria
Posts:79
Joined:Thu Feb 28, 2013 11:49 pm

Re: IMO Shortlist 2004 N6

Unread post by Fm Jakaria » Thu Dec 25, 2014 1:09 am

$P_1 = 1, P_2 = 1$. Let $n > 2$. Set $S_n = (x \in Z_n : x^2 = [1])$. Let $a(n) = |S_n|$.
The idea is to note that $x \in S_n$ and $n-x \in S_n$ are equivalent. Note that all classes in $S_n$ are coprime with $n > 2$. So in case $n$ is even, $\frac{n}{2}$ is not in $S_n$. So of course, $a(n)$ is even, by the pairing. And because $x(n-x)$ is congruent to $-1$ mod $n$;
$P_n = (-1)^{\frac {a(n)}{2}}$. So we only have to determine the parity of $t(n) = \frac{a(n)}{2}$.

We’re going to use standard techniques: if $n$ has PPF = $\Pi p_i^{e_i}$; Chinese remainder theorem implies $a(n) = \Pi a(p_i^{e_i})….(1)$
For some $p_i$ odd, $p_i$ do not divide both $(x+1)$ and $(x-1)$, but divide at least one; where $x \in S_ {p_i^{e_i}}$. So $x$ is $1$ or $-1$ mod $p_i^{e_i}$; giving exactly two solutions $1,-1$ for $x$. So $a(p_i^{e_i}) = 2$.

If some $p_i = 2; a(2) = 1, a(4) = 2$. Let $e_i > 2$. Now for any $x \in S_{p_i^{e_i}}$; $x$ is $1$ or $-1$ mod $2^{e_i-1}$. This is because $x-1$ and $x+1$ has gcd 2 in this case. Each cases gives exactly two solutions mod $2^{e_i}$, giving totally four distinct solutions: $2^{e_i-1} \pm 1, \pm 1$.

So in conclusion: t(n) is even precisely when[by (1)]:
(i) 8|n.
(ii) 4|n and n has at least one odd prime factor.
(iii) n has at least two odd prime factors.
In these cases: $P_n = 1$. Else t(n) is odd and $P_n = -1$.
You cannot say if I fail to recite-
the umpteenth digit of PI,
Whether I'll live - or
whether I may, drown in tub and die.

Post Reply