1
$\begingroup$

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!

$\endgroup$
4
  • 1
    $\begingroup$ 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$? $\endgroup$ Commented Jul 28, 2021 at 4:18
  • $\begingroup$ 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$? $\endgroup$ Commented Jul 28, 2021 at 4:20
  • $\begingroup$ @HagenvonEitzen it is " $<= [n/2] $ " , i'm so sorry , it will be 1,2,3 $\endgroup$
    – abcccccc
    Commented Jul 28, 2021 at 4:28
  • $\begingroup$ @HagenvonEitzen I consider 2 cases : $\varphi (n)$is divisible by $4 $ and $\varphi (n)$is divisible by $2 $.2 cases obtained similar results. $\endgroup$
    – abcccccc
    Commented Jul 28, 2021 at 4:30

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Jul 28, 2021 at 4:38
  • 1
    $\begingroup$ Right, the prime power case has two solutions due to Hensel's lemma, so that's why $n = 9$ didn't work. $\endgroup$
    – Tob Ernack
    Commented Jul 28, 2021 at 4:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .