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$ 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$ Jul 28, 2021 at 4:20
  • $\begingroup$ @HagenvonEitzen it is " $<= [n/2] $ " , i'm so sorry , it will be 1,2,3 $\endgroup$
    – abcccccc
    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
    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$ 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
    Jul 28, 2021 at 4:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.