Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in $\LaTeX$. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

Case 1: n odd Let $n=p_1^{a_1}\ldots p_k^{a_k}$, where $p_i$ are distinct odd primes. Then $P_n=\prod_{S\subseteq [k]}\alpha_S$, where for $S\subseteq[k],\ \alpha_S$ is congurent to $1\pmod{p_i^{a_i}},\ \forall i\in S$, and congruent to $-1\pmod{p_j^{a_j}},\ \forall j\in[k]\setminus S$ ($[k]$ is just a compact notation for $\{1,2,\ldots,k\}$). Since for each $i\in[k]$, there are $2^{k-1}$ subsets $S\subseteq[k]$ for which $\alpha_S\equiv-1\pmod{p_i^{a_i}}$, it means that $P_n\equiv (-1)^{2^{k-1}}\pmod {p_i^{a_i}},\ \forall i$, and thus $P_n\equiv(-1)^{2^{k-1}}\pmod n$. In other words, if $n$ is odd, the answer is $1$ if $n$ has at least $2$ prime divisors, and $-1$ if it's a prime power. Case 2: n even, but not a power of $2$ Let $n=2^ap_1^{a_1}\ldots p_k^{a_k}$, and let $\tilde n=\frac n{2^n}$. The possibilities for $x\pmod{\tilde n}$ are those from the preceding paragraph, while those for $2^a$ are $x\equiv 1\pmod 2$ if $a=1$, $x\equiv \pm1\pmod 4$ if $a=2$, and $x\equiv \pm 1,2^{a-1}\pm 1\pmod{2^a}$. Since $\pm 1,2^{a-1}\pm 1$ give $1\pmod{2^a}$ when squared, and each situation appears $2^k$ times, so an even number of times (since $k\ge 1$), it means that $P_n\equiv 1\pmod{2^a}$, no matter what $a$ is. When $a\ge 2$, each residue $\pmod{\tilde n}$ appears an even number of times, so $P_n\equiv 1\pmod n$ whenever $n=2^ap_1^{a_1}\ldots p_k^{a_k},\ k\ge 1,a\ge 2$. When $a=1$, $P_n$ gives $-1\pmod{\tilde n}$ if $k=1$, and $1\pmod{\tilde n}$ if $k\ge 2$, so $P_n\equiv -1\pmod n$ if $k=1$, and $1\pmod n$ if $k\ge 2$. Case 3: n is a power of $2$ If $n=2$, then the answer is $1$, if $n=4$ it's $-1$, and if $n=2^a,a\ge 3$, then we have $P_n\equiv 1\cdot(-1)\cdot(2^{a-1}-1)\cdot(2^{a-1}+1)\pmod{2^a}$, so $P_n\equiv 1\pmod n$. I hope it's Ok.

The answer can be phrased as $P_n = n-1$ when $n=2, 4, p^k, 2p^k$ for some odd prime $p$ and positive integer $k$; and $P_n=1$ otherwise. Recall that only the numbers of the form $2, 4, p^k, 2p^k$ have primitive roots. Is there a relationship between the two results?

yes there is, the groups formed by the residues of those numbers over multiplication only have 2 elements of order $2$, while the others have more than $2$, and it makes the problem a simple corollary from some abstract algebra result!

This problem was used as problem 6 on the final exam of the 3rd TST of Taiwan 2005.

I think I have a nicer solution for this. (Previously posted in my blog, here.) Notice that, if $x^2 \equiv 1 \pmod n$ then $(n-x)^2 \equiv 1 \pmod n$. Now, $\frac n2^2 \not \equiv 1 \pmod n$ for any $n>2$, so we can assume $x\not \equiv (n-x) \pmod n$ From now on , all congruences are taken $\pmod n$ unless otherwise stated. Now, \[P_n \equiv \prod_{i=1}^{i^2 \equiv 1, i<n} i \equiv \prod_{i=1}^{i^2 \equiv 1, i<\frac n2} i(n-i) \equiv \prod_{i=1}^{i^2 \equiv 1, i<\frac n2}(-1) \pmod n\] Let $f(n)$ be the number of $0<i<n$'s such that $i^2 \equiv 1 \pmod n$. Then $P_n \equiv (-1)^{\frac{f(n)}2} \pmod n$. Now, we will prove some lemmas to find $f(n)$. Lemma 1: $f(n)$ is multiplicative. Proof: Let $p,q$ be positive integers such that $p^2 \equiv 1 \pmod x$ and $q^2 \equiv 1 \pmod y$ with $p<x,q<y$. Then , if $(x,y)=1$, we get $(pq)^2 \equiv 1 \pmod {xy}$ and $pq < xy$. So, $f(xy)=f(x)f(y)$ for $(x,y)=1$. Lemma 2: $f(p^i)=2 \forall \text{ prime }p >2$ Proof: Let $x^2 \equiv 1 \pmod {p^i}$. So $p^i \mid (x+1)(x-1)$ Let $p^k \mid x+1 , p^{i-k} \mid x-1$. But $(x+1)-(x-1)=2$, so one of $k,i-k$ must be $0$. So $x+1 \equiv \pmod {p^i}$ or $x-1 \equiv \pmod {p^i}$. The first part implies $x=p^i-1$, the second part implies $x = 1$. So $f(p^i)=2$ for prime $p >2$. It is easy to see that $f(2)=1,f(4)=2$ and $f(2^j)=4$ for $j>2$. So we get from lemma 1,2, and the fact stated above that, If $n = \prod {p_i}^{e_i}$, then $f(n) = \prod f({p_i}^{e_i})$,with $f(p^x) = 2$ for prime $p>2$, $f(2^x)=4$ for $x>2$, and $f(2)=1,f(4)=2$. So, we get from \[P_n \equiv (-1)^{\frac{f(n)}2} \pmod n\] that \[P_n=\{\begin{matrix} n-1 & \text{for } n=p^k \text{ or } n=2p^k\\ 1 & \text{for all other x} \end{matrix}\] And, we are done.

Mahi wrote: Lemma 1: $f(n)$ is multiplicative. Proof: Let $p,q$ be positive integers such that $p^2 \equiv 1 \pmod x$ and $q^2 \equiv 1 \pmod y$ with $p<x,q<y$. Then , if $(x,y)=1$, we get $(pq)^2 \equiv 1 \pmod {xy}$ and $pq < xy$. So, $f(xy)=f(x)f(y)$ for $(x,y)=1$. How did you get $(pq)^2 \equiv 1 \pmod {xy}$ ?

I have split the problem into cases: Case 1:n is odd Let $n=\prod_{i=1}^{r}{{p_i}^{\alpha_i}}$ where the $p_i$ are odd primes.Then it is easy to see that the only incongruent numbers satisfying $x^2 \equiv 1\pmod{{p_i}^{\alpha_i}}$ are $x \equiv -1,1\pmod{{p_i}^{\alpha_i}}$.This occurs for for all the $r$ powers of form ${p_i}^{\alpha_i}$.Now we will group the residues as follows:replace $1$ by $-1$ and vice versa.For example for $r=3$ the residue group $(1,-1,-1)$ is changed to $(-1,1,1)$.Note that if $x_0$ is a solution to the following congruences $x \equiv 1 \pmod{{p_1}^{\alpha_1}}$ $x \equiv -1\pmod{{p_2}^{\alpha_2}}$ $x \equiv -1\pmod{{p_3}^{\alpha_3}}$ and $x_1$ is a solution to the congruences $x \equiv -1\pmod{{p_1}^{\alpha_1}}$ $x \equiv 1 \pmod{{p_2}^{\alpha_2}}$ $x \equiv 1 \pmod{{p_3}^{\alpha_3}}$ then $x_0x_1 \equiv -1\pmod{n}$.This occurs in general for two solutions of $x_0$ and $x_1$ of the complementary residue sets.There are $2^r$ total residue sets,so if we group them in this way there would be $2^{r-1}$ pairs.Hence the product of all the elements will be $(-1)^{2^{r-1}}$ which is $1$ for $r \ge 2$ and $-1$ for $r=1$. Case 2:$n$ is even but not a power of $2$ Here $n$ can be written as $2^k \prod_{i=1}^{r}{{p_i}^{\alpha_i}}$.Let $k \ge 3$.Then $x^2 \equiv 1\pmod{2^k}$ has four incongruent solutions:namely $1,-1,2^{k-1}-1,2^{k-1}+1$(Its easy to check that they are distinct).We pair the residue sets as follows:replace $2^{k-1}-1$ with $2^{k-1}+1$,$1$ with $-1$ and vice versa modulo $2^k$ and for the other primes replace $1$ with $-1$ and vice versa.Then it is clear that if $x_0$ is a solution of a residue set and $x_1$ is a solution of its complementary residue set we have $x_0x_1 \equiv -1\pmod{n}$.There can be $2^{r+2}$ residue sets and hence $2^{r+1}$ pairs.Consequently $P_n=(-1)^{2^{r+1}}=1$. If $k=1$ then there are $2^{r-1}$ residue set pairs and so $P_n=1$ if $r \ge 2$ and $P_n=-1$ if $r=1$ If $k=2$ then there are $2^r$ residue set pairs and $P_n=1$ Case 3:$n$ is a power of $2$ This is a trivial case.If $n=2^k$ then $P_n=1$ if $k \ge 3$ and $P_n=-1$ if $k$ is $1$ or $2$ Combining these three cases we get $P_n=n-1$ if $n=2,4,p^k,2p^k$ where $p$ is an odd prime and $P_n=1$ otherwise.

orl wrote: Given an integer ${n>1}$, denote by $P_{n}$ the product of all positive integers $x$ less than $n$ and such that $n$ divides ${x^2-1}$. For each ${n>1}$, find the remainder of $P_{n}$ on division by $n$. Proposed by John Murray, Ireland The answer is $\boxed{P_n \equiv -1 \pmod n \text{ if n has a primitive root and 1 otherwise.}}$ Denote $S_n=[x \in N|x \le n,n|x^2-1]$ Observe that if $x \in S$ so is $n-x$ so $P_n \equiv x(n-x) \equiv (-1)^m$ where $S_n$ has $2m $ elements. Now it is just casework:- Case #1: $n$ is odd. Let $n=\prod_{i=1}^{r}{{p_i}^{\alpha_i}}$ where the $p_i$ are odd primes. By CRT,choose $x_0$ to be a solution to the following congruences $x \equiv 1 \pmod{{p_1}^{\alpha_1}}$ $x \equiv -1\pmod{{p_2}^{\alpha_2}}$ $x \equiv -1\pmod{{p_3}^{\alpha_3}}$ and $x_1$ be a solution to the congruences $x \equiv -1\pmod{{p_1}^{\alpha_1}}$ $x \equiv 1 \pmod{{p_2}^{\alpha_2}}$ $x \equiv 1 \pmod{{p_3}^{\alpha_3}}$ then $x_0x_1 \equiv -1\pmod{n}$.Since this occurs for any two numbers which are in the residue class modulo $n$ and there are $2^r$ total residue sets,it follows that there would be $2^{r-1}$ pairs.Hence the product of all the elements will be $(-1)^{2^{r-1}}$ which is $1$ for $r \ge 2$ and $-1$ for $r=1$. Case #2:- $n$ has a prime factor other than $2$ Write $n=2^k \prod_{i=1}^{r}{{p_i}^{\alpha_i}}$ Similar to the previous case,pairing residue classes gives $2^{r+1}$ pairs. Case #3:- $n=2^k$ Here,$P_n=1$ if $k \ge 3$ and $P_n=-1$ if $k$ is $1$ or $2$ Combining the above possibilities,we get the result.$\blacksquare$

Let $S$ denote the set of all $x<n$ such that $n$ divides $x^2-1.$ Fuethermore, let $S^*$ be the set of $x$ in $S,$ strictly smaller than $n/2.$ Assume that $n>2.$ Then, $n/2\notin S,$ so $S^*\cap(S\setminus S^*)=\emptyset.$ The trick is to see that $s\in S^*\iff n-s\in S\setminus S^*.$ It follows that \[\prod_{s\in S}s=\prod_{s\in S^*}s(n-2)\equiv \prod_{s\in S^*}-s^2\equiv (-1)^{|S^*|/2}\bmod{n}.\]We used that if $s\in S^*\subset S$ then $n\mid s^2-1$ so $s\equiv 1\bmod{n}.$ Fuethermore, observe that $|S^*|/2=|S|/4.$ Now, let $n=2^t\cdot p_1^{k_1}\cdot...\cdot p_m^{k_m}.$ Observe that each $s\in S$ is the solution to one of the following congruences, for a suitable choice of $\pm1$ \[s\equiv \pm 1\bmod{2^t}, \quad 2\equiv\pm 1\bmod{p_1^{k_1}} \quad ... \quad s\equiv \pm 1\bmod{p_m^{k_m}}.\]Now, by the CRT, each choice of plusses and minuses yields a unique $s\in S.$ Hence, $|S|$ is equal to the number of choices of $\pm 1$ in the above system of congruences. That number is equal to $f(t)\cdot 2^m.$ where $f(i)=1$ if $i=0,1$ and $f(i)=2$ otherwise. That little change comes because $-1$ and $+1$ are, in fact, the same residue modulo $2$ so changing the sign won't yield a different result. Now, to finish, note that $|S|=2^m\cdot f(t)=2$ only for $n=p^k$ or $2p^k.$ Otherwise, $4\mid 2^m\cdot f(t).$ Therefore, the answer is: $-1$ if $p^k$ or $2\cdot p^k$ and $+1$ for all other $n$. (In lesser words, $-1$ if $n$ admits a primitive root and $+1$ otherwise)

Solved with megarnie. Firstly, note that if $x$ works, then $n-x$ works. Then $x(n-x)\equiv -x^2\equiv -1\pmod n$, so if we just pair the possible $x$'s up, the problem reduces to finding the remainder when the number of possible $x$ is divided by $4$. Particularly, if $x=\frac n2$, then $$n|(x^2-1)\rightarrow (2x)|(x^2-1)\rightarrow x|(x^2-1)\rightarrow x=1\rightarrow n=2,$$where $P_2$ is just $1$. So, define $f(n)$ to be the number of $x$ that work for a given $n$. We first examine when $4|n$. If $n=4$, then $f(4)=2$. Otherwise, there exists quadruples $\left(x,\frac n2-x,\frac n2+x,n-x\right)$ for $x<\frac n4$ such that if one of them work, all four of them work. Note that if $x=\frac n4$, then $$n|(x^2-1)\rightarrow (4x)|(x^2-1)\rightarrow x|(x^2-1)\rightarrow x|1\rightarrow x=1\rightarrow n=4,$$contradiction. So $4|f(4a)$ for positive integers $a>1$. Lemma 1. For odd primes $p$ and positive integers $r$, $f\left(p^r\right)=2$. Proof. Note that $p^r|(x+1)$ or $p^r|(x-1)$, since $p\nmid\gcd(x+1,x-1)$ from the Euclidean algorithm. $1$ and $p^r-1$ clearly work, so $f\left(p^r\right)=2$. Lemma 2. For odd $n\ge 3$, $f(n)=f(2n)$. Proof. Consider the set $S$ of all $x$ that work for $n$. Then the set that work for $2n$ has to be a subset of $T=S\cup (S+n)$. However, for any $x\in S$, note that $\{x,x+n\}$ forms a complete residue set mod $2$. So one of them has an odd square, and the other one has an even square. Since both clearly have a square that is $1$ mod $n$, exactly one of them work. So the number of $x$ that work are actually equivalent for $n$ and $2n$, which is what we wanted. Lemma 3. For odd prime $p$, positive integer $r$, and positive odd $n>2$ such that $p\nmid n$, $4|f(p^r n)$. Proof. Consider the set $S$ of all $x$ that work for $n$. Then the set that work for $p^r n$ has to be a subset of $T=S\cup (S+n)\cup\dots\cup(S+(p^r-1)n)$. However, for any $x\in S$, note that $\{x,x+n,\dots,x+(p^r-1)n\}$ forms a complete residue set mod $p^r$, which must have $f(p^r)$ of them square to $1$ mod $p^r$. Since everything in the set clearly have a square that is $1$ mod $n$, $f(p^r)$ of them work by CRT. But since there are $|S|$ different such $x$'s, $f(p^r n)=|S|f(p^r)=f(n)f(p^r)$, and since both factors on the RHS are even, we have what we wanted. Thus, by repeatedly applying these three lemmas with $r=1$, we can see that for squarefree numbers $n$, $$f(n)\equiv\begin{cases} 1&\qquad\text{if }n=2 \\ 2&\qquad\text{if }n\text{ has }1\text{ odd prime factor} \\ 0&\qquad\text{if }n\text{ has }2\text{ or more odd prime factors} \\ \end{cases}\pmod{4}.$$ Our final case is then if $n$ is not squarefree and not a multiple of $4$. From lemma 2, we can just consider such odd $n$ and extend it to $2n$ later. Using $r>1$ cases from lemmas 1 and 3, when $n$ is not squarefree and not divisible by $4$, $$f(n)\equiv\begin{cases} f\left(\frac n2\right)&\qquad\text{if }2|n \\ 2&\qquad\text{if }n\text{ is a power of an odd prime} \\ 0&\qquad\text{if }n\text{ is odd but not a power of an odd prime} \\ \end{cases}\pmod{4}.$$ So, finally, combining all of these cases, here are our answers. $$\boxed{P_n=\begin{cases} n-1&\qquad\text{if }n\in\{4,p^k,2p^k\}\text{ for odd primes }p\text{ and positive integers }k \\ 1&\qquad\text{otherwise} \end{cases}}$$

Idk why but the solutions to all these look complicated. I will just give the idea of my solution. If $n=2$, then the answer is $1$. Call $x$ good iff $n \mid x^2-1$. Now $x$ is good iff $-\frac1x$ is good. And also see that if $n>2$, then $x \not \equiv -\frac1x \pmod n$, and so we just have to count the number of self inverses modulo $n$ and the pair them up. See that we can easily do it by CRT, since if for some $q \mid n$ where $q$ is an odd prime, then we have \[q^{v_q(n)} \mid x^2-1 \implies q^{v_q(n)} \mid x+1 \text{ or } q^{v_q(n)} \mid x-1\]Let $k$ is the number of odd prime factors of $n$. See that: $\bullet$ If $n$ is odd, then the number of self inverses is $2^k$. $\bullet$ If $v_2(n)=1$ and $n>2$, then again it is $2^k$. $\bullet$ If $v_2(n)=2$, then it is $2^{k+1}$. $\bullet$ If if $v_2(n) \geq 3$, then it is $2^{k+2}$. Now pairing them up we get the answer as \[\boxed{P(n) = \begin{cases} -1 \text{ when } n=4, \text{ } p^a \text{ or } 2p^b \text{ where $p$ is an odd prime and } a,b \in \mathbb{N} \\ +1 \text{ otherwise} \end{cases}}\]

Note that for $n \ge 3$, we have that $\left(\frac{n}{2} \right)^2 \not \equiv 1 \pmod n$, and also that if $x$ works so does $n-x$, therefore we will pair those elements, from now consider everything $\pmod n$. Let $S$ be the set of all such $x$. \[P_n=\prod_{\substack{j \in S \\ 1 \le j \le n-1}} j=\prod_{\substack{j \in S \\ 1 \le j \le \left \lfloor \frac{n}{2} \right \rfloor}} j(n-j)=\prod_{\substack{j \in S \\ 1 \le j \le \left \lfloor \frac{n}{2} \right \rfloor}} -j^2=(-1)^{\frac{|S|}{2}} \]Now note that if $x=2^{s} \cdot p_1^{\alpha_1} \cdots p_i^{\alpha_i}$ where the $p_j$'s are odd primes, then whenever $x \in S$ then by CRT it means that $x$ satisfies these: \[ x \equiv \pm 1 \pmod{2^s} \; \text{and} \; x \equiv \pm 1 \pmod{p_1^{\alpha_1}} \; \cdots \; x \equiv \pm 1 \pmod{p_i^{\alpha_i}} \]Therefore the number of all elements in $S$ is all the possible choices from this CRT system which are $2^{i+1}$ when $s \ge 2$ and if $s=0,1$ then it's $2^i$, so all we need is to figure out $|S| \pmod 4$ but for $i \ge 2$ or when $s \ge 2$ and $i \ge 1$, it is $0$ which means that $P_n \equiv 1 \pmod n$, and it's $2$ when $s \le 1$ and $i=1$ or when $s \ge 2$ but $i=0$ in which case $P_n \equiv -1 \pmod n$. And finally if $n=2$ then only $x=1$ works so the product is $1$, therefore we are done .

what Let $n = 2^i \prod p_i^{e_i}$ where the $e_i \ge 1$. First suppose $i \ge 2$. Then it is well known that \[ (\mathbb Z / n\mathbb Z)^\times \cong (\mathbb Z / 2^{i-2} \mathbb Z) \times (\mathbb Z / 2 \mathbb Z) \times \prod (\mathbb Z / p_i^{e_i-1}(p_i - 1) \mathbb Z). \]If $i=1$ or $i=0$, then \[ (\mathbb Z / n\mathbb Z)^\times \cong \prod (\mathbb Z / p_i^{e_i-1}(p_i - 1) \mathbb Z). \]Let $k$ be the number of factors on the right hand side. Clearly $k \ge 1$. Then the subgroup generated by elements of order $2$ is isomorphic to \[ (\mathbb Z / 2 \mathbb Z)^k. \]Particularly, if $k \ge 2$, then the product of all the elements is the identity; this is readily verified by counting the elements which have $1$ in a given coordinate. If $k=1$, then the product is just the singular element of order $2$. This leaves us with the answer of $-1$ if $n=4$ or is a prime power or is twice a prime power, and $1$ otherwise.