I have to show that if $n = p_1^{a_1}...p_u^{a_u} = 2^dm +1$ is odd and composite (with at least 2 primes dividing n) then the number of integers $k$ such as $1 \leq k \leq n$ and not satisfying the following test :
The test is satisfied when one of the two following conditions are satisfied
- $k^m = 1 [n]$
- It exists $0 \leq s \leq d-1$ such as $k^{2^sm + 1} = -1 [n]$
is greater than $n(1 - 2^{1 - u}) \geq 3n/4$ (where $u$ is the number of primes dividing $n$)
I showed (with remainder chinese theorem) that the equation $\alpha^2 = 1$ has $2^u$ solutions modulo $n$. In my exercise, it seems that the result is a consequence of the precedent question but I don't see how to conclude
