3
$\begingroup$

I came across this exercise in solving a modular congruence:

Find an integer $0\le x<527$ such that $$x^{37}\equiv3\mod527$$

but being fairly new to this branch of number theory (and the topic in general), I'm not sure how to proceed. My current knowledge doesn't exceed what I've gleaned from the Wikipedia article on modular arithmetic and a few examples I've worked out involving the Euclidean algorithm.

Attempt: I thought to simplify the above slightly by considering the congruence

$$3y\equiv1\mod527$$

then via the Euclidean algorithm found the modular inverse to be $y=176$; easy enough.

Then multiplying by $3$ gives

$$9y\equiv3\mod527$$

suggesting that the solution to my problem satisfies $x^{37}=1584$. But I'm hitting a wall, and I don't even know whether this is correct to begin with.

Wolfram|Alpha tells me I should arrive at $x=148$, which makes me think my reasoning above isn't valid or that what I'm doing simply isn't productive. Is there a "right" method I should be using?

$\endgroup$
4
$\begingroup$

Use the Chinese Remainder Theorem, noting that $527=17\times31$. Thus $$x^{37}\equiv3\pmod{527}$$ is equivalent to $$x^{37}\equiv3\pmod{17}\quad\hbox{and}\quad x^{37}\equiv3\pmod{31}\ .$$ By Fermat's Little Theorem (terms and conditions apply) $a^{p-1}\equiv1\pmod p$, so these are equivalent to $$x^5\equiv3\pmod{17}\quad\hbox{and}\quad x^7\equiv3\pmod{31}\ .$$ Now these are small enough to solve by trial and error (alternative: see below), giving $$x\equiv-5\pmod{17}\quad\hbox{and}\quad x\equiv-7\pmod{31}\ ,$$ and then the standard CRT procedure gives $$x\equiv148\pmod{527}\ .$$


Alternative way to solve $x^5\equiv3\pmod{17}$: raise to the power $s$ such that $x^{5s}\equiv x\pmod{17}$. This requires $5s\equiv1\pmod{16}$ and we may take $s=13$. So $$x^5\equiv3\quad \Rightarrow\quad x\equiv x^{65}\equiv(x^5)^{13}\equiv3^{13}\pmod{17}$$ and we calculate $$3^2\equiv9\ ,\quad 3^4\equiv9^2\equiv81\equiv-4\ ,\quad 3^8\equiv(-4)^2\equiv16\equiv-1$$ and finally $$3^{13}\equiv3^8\times3^4\times3^1\equiv12\equiv-5\pmod{17}\ .$$

$\endgroup$
  • $\begingroup$ "Now these are small enough ..." I'm not sure I follow this part. What constitutes "small enough"? Is it the solution to $x^5\equiv3\pmod{17}$ that happens to be small enough? or something to do with the modulus? $\endgroup$ – user170231 Jun 7 '17 at 17:01
  • $\begingroup$ "Small enough" means small enough for me to solve by trying values of $x$. If not small enough for you, then use the alternative method. $\endgroup$ – David Jun 8 '17 at 0:00
  • $\begingroup$ Regarding the alternative method, why do we need to have $5s\equiv1\pmod{16}$? It's no coincidence that the same value of $s$ is needed to satisfy $7s\equiv1\pmod{30}$, but I don't see the reasoning behind this requirement in the first place. (I'd be happy to ask this as another question if that's more appropriate.) $\endgroup$ – user170231 Jun 12 '17 at 22:29
  • $\begingroup$ $x^{16}\equiv1\pmod{17}$, so $x^{5s}\equiv x$ if $5s\equiv1\pmod{16}$. $\endgroup$ – David Jun 14 '17 at 0:01
  • $\begingroup$ Okay, I see now that the 16 is coming from applying little Fermat. Many thanks! $\endgroup$ – user170231 Jun 14 '17 at 0:32

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.