Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
Do it mod 7 and mod 19, then use Chinese remainder theorem. –  Soarer Sep 15 '11 at 1:46
    
$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. –  Aaron Sep 15 '11 at 1:51
1  
And even the original $2^{133}$ is $2^{2^7}\times 2^5$, which can be done in less than ten modular multiplications. –  Henning Makholm Sep 15 '11 at 1:58
    
@Foolmath: I don't understand your point. Do $x \equiv a$ and $a \equiv x$ feel different to you? –  Soarer Sep 15 '11 at 2:05
    
@Soarer:I get your point,but using CRT isn't really fast approach for this problem I guess. –  Quixotic Sep 15 '11 at 2:38

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
1  
what is odd primes?I didn't understand your approach at all :/ –  Quixotic Sep 15 '11 at 3:38
1  
@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$. –  Ted Sep 15 '11 at 3:55
    
@Foo I've appended a complete proof below the hint. –  Bill Dubuque Sep 15 '11 at 4:38

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

share|improve this answer
    
+1,I understood this approach,for the last part I used CRT,however not much a fast way I guess. –  Quixotic Sep 15 '11 at 2:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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