Find a cube root of 97mod101 gracefully.

I don't really know where to get started...could someone help me? I don't expect you to do the calculations, but could you give me a hint written out in words on how to get started?

  • $\begingroup$ With a bit of luck, $97+101k$ is a perfect cube for some smallish $k$. $\endgroup$ – Harald Hanche-Olsen Oct 21 '14 at 9:05

I will present two solutions. The key to the first solution is to observe that $$ 97\equiv-4=(-1)^32^2\pmod{101}. $$ What this means is that if we can find a modular cube root $u$ of $2$, then we are in business, because $u^2$ will be a cube root of $4$, and the minus sign won't pose a problem either.

In the spirit of rudimentary index-calculus we can try and do a little bit of testing. The goal is to find modular cube roots for enough many numbers with only small prime factors so that we can solve for the cube root of two. This depends on a bit of luck.

Today is our lucky day, because we see that $$ 6^3=216\equiv 14=2\cdot7\pmod{101} $$ and $$ 8^3=512\equiv7\pmod{101}. $$ So we have cube roots for both $2\cdot7$ and $7$. Well... This implies that $u=(6\cdot8^{-1})$ satisfies $u^3\equiv2$. Here $8^{-1}=38$ is the modular inverse of $8$ modulo $101$ ($1\equiv 304=4\cdot76=8\cdot38$). Thus $$ u=6\cdot38=228\equiv 26. $$

As a final step we calculate that the cube root of $97=-4$ is $-u^2=-676\equiv31$.

A more general (and less ad hoc) method would be to observe that:

  1. $p=101$ is a prime such that $3\nmid(p-1)$.
  2. By Little Fermat $a^{100}\equiv1\pmod {101}$ whenever $a$ is not a multiple of $101$.
  3. $201=67\cdot3$ (or $67=3^{-1}$ modulo $100$).
  4. Therefore for all $a$ coprime to $101$ $$(a^{67})^3=a^{201}=a^{200}\cdot 1=(a^{100})^2a\equiv1^2a=a\pmod{101}.$$

This tells us that $97^{67}$ will serve in the role of the cube root. To quickly calculate that use the good ole square-and-multiply.

  • $\begingroup$ Usually what I called "index-calculus" is a method for solving the discrete logarithms of small primes (or low degree irreducible polynomials over a finite prime field). Here I started a mission to build a table of cube roots of small primes instead, and threw away the stuff that wasn't needed. $\endgroup$ – Jyrki Lahtonen Oct 23 '14 at 20:31

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.