# Find $n \geq 3$ odd such that : ${T_n} ^ 2 \equiv (-1)^{\frac {\varphi (n)}{2}}$

Let $$T_n$$ be the product of numbers less than $$[\frac{n}{2}]$$ and co-prime to $$n$$. Find $$n \geq 3$$ odd such that :

$$T_n^2 \equiv (-1)^{\frac {\varphi (n)}{2}} \pmod n$$

Here is all i did:

It is easy to see that when $$\gcd(a,n) = 1$$, then $$\gcd(n-a,n) =1$$

So we only have to find $$n$$ such that :

$$a_1a_2a_3\cdots a_{\varphi(n)} \equiv 1 \pmod n$$

it is easy to see that $$n$$ cannot be prime according to Wilson's theorem: $$(p-1)! \equiv -1 \pmod p$$

But at this point I have no idea at all, I hope to get help from everyone. Thank you very much everyone!

• Are the brackets in $[\frac n2]$ the floor function? As in $[\frac72]=3$, so for $n=7$, the co-prime numbers less than $[\frac 72]$ are only $1$ and $2$? Jul 28, 2021 at 4:18
• Why should $a_1a_"\cdots a_{\phi(n)}\equiv 1\pmod n$ be either sufficient or necessary for $T_n^2\equiv (-1)^{\phi(n)/2}\pmod n$? Jul 28, 2021 at 4:20
• @HagenvonEitzen it is " $<= [n/2]$ " , i'm so sorry , it will be 1,2,3 Jul 28, 2021 at 4:28
• @HagenvonEitzen I consider 2 cases : $\varphi (n)$is divisible by $4$ and $\varphi (n)$is divisible by $2$.2 cases obtained similar results. Jul 28, 2021 at 4:30

Assuming $$n$$ is odd, using what you observed about pairing $$x$$ with $$-x \pmod n$$, the product of all elements in $$\left(\mathbb{Z}/n\mathbb{Z}\right)^\times$$ is equal to $$(-1)^{\frac{\varphi(n)}{2}}T_n^2 \pmod n$$, so the question is equivalent to finding $$n$$ such that the product of all elements in $$\left(\mathbb{Z}/n\mathbb{Z}\right)^\times$$ is equal to $$1 \pmod n$$.
But you can now pair up every unit with its multiplicative inverse $$x \leftrightarrow x^{-1} \pmod n$$, as long as they are distinct, and you'll get a product of $$1$$. So the only terms contributing to the product are the elements that are solutions to $$x^2 = 1 \pmod n$$.
But $$-1$$ will always be one of these solutions so you will need at least one more nontrivial solution to the equation (you'll actually get two for free because of the $$x \leftrightarrow -x$$ pairing). The first time this happens for $$n$$ odd is when $$n = 3 \times 5 = 15$$, which has solutions $$\pm 1, \pm 4$$.
And indeed, we can check that $$n = 15$$ satisfies the requirements.
• More generally, $x^2\equiv 1\pmod {n}$ has exactly two solutions when $n$ is a power of an odd prime, and if we can write $n$ as product of $k$ such powers, then by the Chinese Remainder Theorem, there are $2^k$ solutions. For our purposes, we need $4\mid 2^k$, i.e., $n$ is not a prime power. Jul 28, 2021 at 4:38
• Right, the prime power case has two solutions due to Hensel's lemma, so that's why $n = 9$ didn't work. Jul 28, 2021 at 4:48