Find $1<a<9991$ such that $ a^{4995}\not \equiv 1 \mod 9991 , a^{4995}\not \equiv -1 \mod 9991 , a^{2\cdot4995}\not \equiv -1 \mod 9991 $

Question

Find $1<a<9991$ such that \begin{align} a^{4995}\not \equiv 1 &\mod 9991 \\ a^{4995}\not \equiv -1 &\mod 9991 \\ a^{2\cdot4995}\not \equiv -1 &\mod 9991 \end{align}

---

I'm having a hard time in finding $a$.
Is there any approach that is not computational?
So far I figured out from third condition that $a$ might be a coprime integer to 9991.

Answer 1

If $\gcd(a,9991) = d> 1$ then $d|9991k + a^m$ for all $k$ and $m$ so $a^m \equiv $ a multiple of $d$ for any power $m$. So $a^m \not \equiv \pm 1 \mod 9991$

So we just need to find a number that is not coprime with $9991$.

So any factor or a multiple of a factor of $9991$ will do. So if we can show that $9991$ is not prime we will be done.

(And if $9991$ is prime then there is no solution as all $a; 1< a<9991$ would be coprime and $a^{2*4995} = a^{9991 - 1}$ would be $ \equiv 1 \mod 9991$.)

So it is necessary and sufficient to show $9991$ is not prime and to find any multiple of a factor of $9991$.

Answer 2

$9991=97\cdot103$, therefore $97$ is not invertible modulo $9991$, and none of its powers can be invertible. Which means none of its powers can be $1$ or $-1$.

Answer 3

" In fact, the goal is to show that 9991 is not prime."

$$ 9991 = 10000 - 9 = 100^2 - 3^2 = (100-3)(100+3) = 97 \cdot 103 $$