Oh my! 100th powers!

Computer Science Level 5

Let N be the number of positive integers m for which

$3^{100}\equiv2^{100} \pmod m$

Then N can be expressed as $2^k$

Find the value of $k$ .

Details For those who don't know Mod notation :

$a\equiv b \pmod c$ if and only if " $a$ " and " $b$ " give the SAME remainder when divided by $c$ .

And this information is enough to find the trick which makes the problem easy.

The answer is 13.

1 solution

Aditya Raut
Mar 22, 2014

Note for those who don't know this notation -

From the given information, anyone can see that

$a\equiv b \pmod c$ ... if c divides (a-b) , because the SAME remainder will get eliminated by subtraction of the numbers ........ That is COMPULSARY ..

Hence $m|(3^{100}-2^{100})$ The number of integers m is same as the number of factors of $3^{100}-2^{100}$ $3^{100}-2^{100}=5^3\times 11 \times 13 \times 101 \times 211 \times 1201 \times 4621 \times 11701 \times 513101 \times 9802501 \times 39756701 \times 104189401$

Hence the number is of the form $p_1^3\times p_2\times p_3\times ... \times p_{11} \times p_{12}$ where $p_i$ are distinct primes

Hence the number of integers for which $3^{100}\equiv2^{100}\pmod m$ is

$(3+1)(1+1)^{11}$ = $2^2\times2^{11}$ = $2^{13}$

Hm, how did you determine the factorization? This might be more of a computer science problem, than a number theory problem.

Calvin Lin Staff - 7 years, 2 months ago

Oh my! 100th powers!

The answer is 13.

1 solution

0 pending reports