4
$\begingroup$

I have to solve this equation $2^{133} \equiv x \mod 133 $.Using Euler's theorem I reduced it to $2^{25} \equiv x \mod 133$ but I couldn't think off any fast way to proceed after this.

Any ideas?

$\endgroup$
7
  • 3
    $\begingroup$ Do it mod 7 and mod 19, then use Chinese remainder theorem. $\endgroup$
    – Soarer
    Sep 15 '11 at 1:46
  • $\begingroup$ $2^{25}=2(2^{3\cdot 8})=2((8^2)^2)^2$. If you compute by doing repeated squaring and reduce mod 133 every time you square, the numbers you work with won't be too big. $\endgroup$
    – Aaron
    Sep 15 '11 at 1:51
  • 1
    $\begingroup$ And even the original $2^{133}$ is $2^{2^7}\times 2^5$, which can be done in less than ten modular multiplications. $\endgroup$ Sep 15 '11 at 1:58
  • $\begingroup$ @Foolmath: I don't understand your point. Do $x \equiv a$ and $a \equiv x$ feel different to you? $\endgroup$
    – Soarer
    Sep 15 '11 at 2:05
  • $\begingroup$ @Soarer:I get your point,but using CRT isn't really fast approach for this problem I guess. $\endgroup$
    – Quixotic
    Sep 15 '11 at 2:38
5
$\begingroup$

HINT $\ $ for primes $\rm\: p\ne q,\ \ p\!-\!1\ |\ q\!-\!1\ \Rightarrow\ c^{q}\equiv\: c\pmod{p\:q}\ $ by Fermat's little Theorem.

So for $\rm\:p,q = 7,19,\ c = 2^7\:$ we infer that $\rm\: 2^{\:7\:\cdot\: 19}\equiv 2^7\equiv 128 \equiv {-}5 \pmod{7\cdot 19}\ \ $ QED

Proof $\ $ Assume $\rm\ p \ne q\ $ are primes and $\rm\: q = 1 + k\:(p-1)\:,\ k\in \mathbb N\:.\: $ By Fermat's little Theorem $\rm\:mod\ q\!:\ c^q = c\:;\ \ \ mod\ p\!:\ c^q =\: c^{\:1+k\:(p-1)} =\: c\ (c^{\:p-1})^{k}\equiv\: c\ $ if $\rm\:c\not\equiv\: 0\:,\:$ and $\rm\:c^q\equiv c\:$ if $\rm\:c\equiv 0\:.\:$
Therefore $\rm\:p,q\ |\ c^q-c\:$ $\:\Rightarrow\:$ $\rm\:lcm(p,q) =\: p\:q\ |\ c^q-c\:.\ \ $ QED

NOTE $\ $ The above proposition is a special case of a general Fermat-Euler-Carmichael Theorem.

Note that this is yet another example of constant case optimization of Chinese Remainder (CRT).

$\endgroup$
3
  • 1
    $\begingroup$ what is odd primes?I didn't understand your approach at all :/ $\endgroup$
    – Quixotic
    Sep 15 '11 at 3:38
  • 1
    $\begingroup$ @FoolForMath: Odd primes means primes that are odd, i.e., bigger than 2. For the first implication: To see that $p | 2^{pq} - 2^p$, apply Fermat's Little Theorem (FLT) for $p$ twice, using the condition $p-1 | q-1$. To see that $q | 2^{pq} - 2^p$, apply FLT for $q$. $\endgroup$
    – Ted
    Sep 15 '11 at 3:55
  • $\begingroup$ @Foo I've appended a complete proof below the hint. $\endgroup$ Sep 15 '11 at 4:38
2
$\begingroup$

Use $133 = 7 \times 19$. Use $2^p = 2 \mod p$ for $p \in \mathbb{P}$.

Now $2^{133} = (2^7)^{19} \mod 7 = 2^{19} \mod 7 = (2^7)^2 \times 2^5 = 2^2 \times 2^5 = 2^7 = 2 \mod 7$. Similarly $2^{133} = (2^{19})^7 = 2^7 = 14 \mod 19$. Thus

Let $x = 2^{133} \mod 133$, then from $x = 14 \mod 19$, it follows that $x = 14 + 19 \times k$. From $x = 2 \mod 7$, it follows $(14 + 19 \times k) = 5 \times k = 2 \mod 7$, and $k = 6 \mod 7$. From this I get $2^{133} = 128 \mod 133$.

$\endgroup$
1
  • $\begingroup$ +1,I understood this approach,for the last part I used CRT,however not much a fast way I guess. $\endgroup$
    – Quixotic
    Sep 15 '11 at 2:28

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.