0

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.

user3342072
  • 791
  • 6
    $9991 = 97 \cdot 103$ – Will Jagy Jun 12 '18 at 23:13
  • 1
    Almost any $a$ will do. Only $777, 1031, 1807, 1808, $ $3915, 4269, 4691, 4692, $ $5299, 5300, 5722, 6076, $ $8183, 8184, 8960 ,9214$ fail one of the first two criteria. No value fails the third criterion. – Joffan Jun 14 '18 at 00:23

3 Answers3

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$.

Arnaud Mortier
  • 27,276
2

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$.

fleablood
  • 124,253
  • Indeed! Thank you! In fact, the goal is to show that 9991 is not prime. – user3342072 Jun 12 '18 at 23:51
  • Well, others have pointed out that $9991 = 97*103$ which can be determined by ... trial and error. I just wanted to justify that that indeed is the end all and be all of the problem. – fleablood Jun 13 '18 at 02:54
  • this is Fermat's factoring method, look at the squares larger than the target number $N$ and see if the difference is a square. If $N = a^2 - b^2 ...$ – Will Jagy Jun 13 '18 at 03:02
  • The question is... is that efficient. Which I guess it is. If $N$ is odd and $N = ab; a < b$ then $N=ab=(\frac {a+b}2 - \frac {b-a}2)(\frac {a+b}2 +\frac{b-a}2)=\frac {a+b}2^2 - \frac{b-a}2^2$. In this case $9991$ is so obviously close to $100^2$ and the difference is $9$ a square. I mean, if we we to show $2347=1081$ is it worth doing? $1081 = 33^2 - 8;34^2- 75;$ etc. It'll be a while before we get to $\frac {23+47}2= 35$ and... oh, wait, it would have been the very next* one to try. $1081 = 35^2 -144 = (35-12)(35+12)$.... But is it efficient. Well,... compared to what? I suppose. – fleablood Jun 13 '18 at 03:24
1

" 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 $$

Will Jagy
  • 139,541
  • Just to clarify. The claim is that if 9991 meets conditions in questions then it's not a prime. So I am forced to show it that way. Noticing that 9991 can be factored out feels like cheating and makes checking conditions pointless, because we finished before we even started. – user3342072 Jun 13 '18 at 10:17
  • @user3342072 Nothing in your question indicated that. – Arnaud Mortier Jun 13 '18 at 11:41