# Find the last digit of the exponent $x$.

Let \begin{align} p&=396543857870745963499374527519378569849832249490600276007703072957912\cdots\\ &\phantom{=}8049490077183813353745228056691 \end{align}

This number is a 100-digit prime number and 2 is a primitive root modulo $p$. Let $x$ be the unique positive integer with $1 \leq x \leq p-1$ so that $2^x \equiv 5 \pmod{p}.$

What is the last digit of $x$?

• How do you know that 2 is a primitive root modulo p? – Lord_Gestalter Dec 11 '14 at 9:03
• @Lord_Gestalter Maple reveals that $p-1=10q$ where $q$ is prime. Further, $2^{2q}$ and $2^{5q}$ both turn out not to be $1$ modulo $p$. – Harald Hanche-Olsen Dec 11 '14 at 10:37
• @HaraldHanche-Olsen That should suffice. Gosh, Maple is dammin' fast. Filed prime lists? – Lord_Gestalter Dec 11 '14 at 11:19
• @Lord_Gestalter No, these primes are too big to be in any list. Maple checks primality for large integers by some probabilistic test like Rabin–Miller, I think. I just used ifactor((p-1)/2), and the answer popped right out. Of course, if $p-1$ had had several large prime factors, Maple might not have finished so quickly. I just had a hunch that this prime was constructed so $p-1$ had only one large prime factor, and that turned out to be right. – Harald Hanche-Olsen Dec 11 '14 at 13:44

## 1 Answer

We can work this out with a little help from any program capable of computing with large integers (I used Maple and Haskell (ghci)):

It turns out that $p-1=10q$ where $q$ is prime. Also, it turns out that $5^{5q}\equiv1\pmod p$, i.e., $2^{5qx}\equiv1\pmod p$. Since $2$ is a primitive root, this implies $5qx\equiv0\pmod{10q}$, and hence $x$ is even.

Edit the second: A bit more playing around (on a hunch) reveals that $2^{2q}\equiv5^{4q}\pmod{p}$, i.e., $2^{2q}\equiv2^{4qx}\pmod{p}$, and therefore $2q\equiv4qx\pmod{10q}$, i.e., $1\equiv2x\pmod5$. Since $x$ is even, we conclude $x\equiv8\pmod{10}$, i.e., the last digit of $x$ is $8$.

• If $5^{2q}\neq1\pmod p$ can't you exclude the 0? – Lord_Gestalter Dec 11 '14 at 14:52
• Yes, but that still leaves four possibilities. – Robert Israel Dec 11 '14 at 15:51
• @Lord_Gestalter You're right; I incorporated it into my answer. Thanks. – Harald Hanche-Olsen Dec 11 '14 at 15:59