7
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ How do you know that 2 is a primitive root modulo p? $\endgroup$ – Lord_Gestalter Dec 11 '14 at 9:03
  • $\begingroup$ @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$. $\endgroup$ – Harald Hanche-Olsen Dec 11 '14 at 10:37
  • $\begingroup$ @HaraldHanche-Olsen That should suffice. Gosh, Maple is dammin' fast. Filed prime lists? $\endgroup$ – Lord_Gestalter Dec 11 '14 at 11:19
  • $\begingroup$ @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. $\endgroup$ – Harald Hanche-Olsen Dec 11 '14 at 13:44
3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.