Let be $n$ an odd integer and $b$ such as $b$ and $n$ are coprimes (i.e. $b \wedge n = 1$).
- If $n$ is divisible by the square of a prime $p$, determine how to find an integer $b$ such as $b \wedge n = 1$ and $b^{(n-1)/2} \not \equiv \pm 1\mod n$.
- We have $n = kp^2$ and we want $b \wedge n = 1$, i.e. $b \wedge k = 1$ and $b \wedge p = 1$. But we also want $b^{(n-1)/2} \not \equiv \pm 1\mod n$, and $b^{(n-1)/2} \equiv (\frac{b}{n}) \mod n$ so it would mean that $(\frac{b}{n}) = 0$, i.e. $b | n$... What am I misunderstanding here?
- If $n = pq$ with $p$ and $q$ two distincts primes and $a$ an integer such as $(\frac{a}{n}) = -1$ and $a \equiv 1 \mod q$. Determine that the relation $(\frac{b}{n}) \equiv b^{(n-1)/2} \mod n$ is false for a such $a$. Prove that a such $a$ still exists.
- Here we can start by saying that $(\frac{a}{n}) = -1$ because $(\frac{a}{p}) = -1$ and $(\frac{a}{q}) = 1$. But then how to prove that $b^{(n-1)/2} \not \equiv -1\mod n$?