7
$\begingroup$

Compute $$(3^{999^{100}} + 7^{960^{961}}) \bmod 225. $$

I first computed the left expression, and eventually found it, but it took me like an hour, so I was wondering if there is no faster way. First I wrote $$3^{999^{100}} \bmod 225 = (3^{999} \bmod 225)^{100} \bmod 225. $$ I noticed that $225 = 3 \cdot 75 = 3 \cdot (3 \cdot 25)$. So I tried working on the system $$ \begin{cases} 3^{999^{100}} \bmod 25 = 0 \\ (27^{333} \bmod 25)^{100} \bmod 25 \end{cases}$$ and then using Chinese Remainder theorem. For the last equation, We have $27^{333} \equiv 2^{333} \equiv (8^{111} \bmod 25)^{100} \bmod 25. $ To compute $(8^{111} \bmod 25)$, I just kept squaring, computing $8^2, 8^4, 8^8$ etc, and taking the modulo each time. Eventually I found $8^{111} \equiv 17 \bmod 25$. Then I needed to find $$17^{100} \bmod 25 \equiv (17^4 \cdot 17^{25} ) \bmod 25. $$ By squaring again I found the answer as $22 \bmod 25$. So I used the Chinese Remainder theorem to find the solution of $$ \begin{cases} x \bmod 25 = 22 \\ x \bmod 3 = 0 \end{cases}$$ which gave me $x = 72$. So I managed to find $$3^{999^{100}} \bmod 225 = 72 \bmod 225. $$ Now, I was wondering if there is no better trick/faster way to find the correct answer by hand (no calculator), since I'm not looking forward to doing another hour of computation to find the second expression. Thank you in advance.

Later addition: With the help of Arthurs hints: We have $225 = 9 \cdot 25$. Hence for the first expression I have the system $$ \begin{cases} 3^{999^{100}} \bmod 9 = 0 \\ 3^{999^{100}} \bmod 25 = a. \end{cases}. $$ I want to find $a$ now. I have $\phi(25) = 20$, so $3^{20} \bmod 25 = 1 \bmod 25$ by Euler. Now I wanted to write the exponent $999^{100}$ as a multiple of $20$. I have $3^{(20 \cdot (50-1))^{100}} = 3^{20^{100} \cdot (50-1)^{100}} = (3^{20})^{(20^{99} \cdot (50-1)^{100})}$. So taking the modulo would give me $1$?

$\endgroup$
  • $\begingroup$ First of all, $3^{999^{100}}$ is a very different animal from $(3^{999})^{100}$, even when modding out in-between. Don't mix them up. Second, have you heard about Euler's theorem? $\endgroup$ – Arthur Aug 14 '16 at 10:02
  • $\begingroup$ @Arthur, of course. But I'm not sure how to use that here. Congruence of Euler: if $gcd(a,n) = 1$, then $a^{\phi(n)} \equiv 1 \mod n$. But how do I find $\phi$ of large exponents? $\endgroup$ – Kamil Aug 14 '16 at 10:04
  • $\begingroup$ The relevant totient exponent is $\phi(225)=120$. So you would need to find $999^{100}\mod{120}$, which again is possible using Euler's theorem. $\endgroup$ – Arthur Aug 14 '16 at 10:07
  • $\begingroup$ But $3$ and $225$ are not coprime. $\endgroup$ – Kamil Aug 14 '16 at 10:16
  • $\begingroup$ Right. For some reason I thought $225$ was a power of $5$. However, after using the Chinese remainder theorem, you get a huge power of $3$ modulo $9$, which is certainly $0$, and a huge power of $3$ modulo $25$, which can be found using Euler's theorem with $\phi(25)=8$, which is certainly doable within minutes. $\endgroup$ – Arthur Aug 14 '16 at 10:20
2
$\begingroup$

To compute $\;3^{999^{100}}$ faster, use Euler's theorem: $\;\varphi(25)=20$, so $$3^{999^{100}}\equiv3^{999^{100}\bmod20}\equiv3^{(999\bmod20)^{100}}\equiv3^{(-1)^{100}}=3\mod25.$$

As a Bézout's relation between $9$ and $25$ is $\;-11\cdot 9+4\cdot 25=1$, the solutions of the system of congruences $\;\begin{cases} x\equiv 0\mod 9,\\x\equiv 3\mod 25, \end{cases}\;$ is: $$x\equiv-3\cdot11\cdot 9+0\cdot4\cdot 25=-297\equiv-72\mod 225.$$

$\endgroup$
  • 1
    $\begingroup$ You must have a sign error somewhere since my answer shows that $\,x\equiv -72\pmod{225}\,$ is correct $\ $ $\endgroup$ – Bill Dubuque Aug 14 '16 at 16:34
  • $\begingroup$ The glitch is in the Bézout relation. $\endgroup$ – quid Aug 14 '16 at 16:37
  • $\begingroup$ @quid: Oh yes. Is hould have checked my computations. Thanks! $\endgroup$ – Bernard Aug 14 '16 at 17:11
  • $\begingroup$ @Bill Dubuque: quid found out the error. Fixed. Thanks for pointing it! $\endgroup$ – Bernard Aug 14 '16 at 17:13
4
$\begingroup$

Finding a number $a$ that satisfy $$3^{999^{100}}+7^{960^{961}}\equiv a\pmod {225}$$ is equivalent to solving the system $$\begin{cases}3^{999^{100}}+7^{960^{961}}\equiv a\pmod {9}\\\\3^{999^{100}}+7^{960^{961}}\equiv a\pmod {25}\end{cases}.$$ Edit: I add a proof of the above claim here. You can skip this if you know the proof.

To prove the equivalence, we consider the general case $$a\equiv b\pmod n$$ and let $$n=\prod_{i=1}^{m}{p_i}^{k_i}$$ be the prime decomposition of $n$. Since $n\mid a-b$ and ${p_i}^{k_i}\mid n$ for each of $i=1,2,...,m$, we immediately have ${p_i}^{k_i}\mid a-b$. This proves that the original congruence implies the system of congruences.

For the converse, suppose ${p_i}^{k_i}\mid a-b$ for each of $i=1,2,...,m$. That is, we assume the system of congruences holds. Using this theorem, since the prime powers are coprime, you can show inductively that the whole product divides $a-b$. That is, $$\prod_{i=1}^{m}{p_i}^{k_i}\mid a-b.$$ But the product is just equal to $n$. So $n\mid a-b$. This proves that the system of congruences implies the original congruence.

We now simplify each of the congruences. It is easy to see that $3^{999^{100}}$ is a multiple of $9$. Since $\phi(9)=6$, and that $960$ is a multiple of $6$, we have $7^{960^{961}}\equiv 7^{6n}\equiv 1\pmod {9}$, where $n=\frac{960^{961}}{6}$ is a positive integer.

For the second congruence, observe that $\phi(25)=20$, and $999^{100}\equiv (-1)^{100}\equiv 1\pmod{20}$, so $999^{100}-1=20m$, where $m=\frac{999^{100}-1}{20}$ is a positive integer. Then $3^{999^{100}}\equiv 3^{20m+1}\equiv 3\pmod{25}$. $960$ is a multiple of $20$. So $7^{960^{961}}\equiv 7^{20k}\equiv 1 \pmod{25}$, where $k=\frac{960^{961}}{20}$. We have arrived at the system $$\begin{cases}a\equiv 1\pmod {9}\\\\a\equiv 4\pmod {25}\end{cases}.$$ You can solve this by Chinese Remainder Theorem.

$\endgroup$
  • $\begingroup$ Could you, please, elaborate why the original congruence relation is equivalent to the system of equations with $(mod \; 9)$ and $(mod \; 25)$? Why not modulo $3$ and $5$? $\endgroup$ – Pixar Aug 14 '16 at 14:39
  • 1
    $\begingroup$ @Pixar Because $225=9\cdot 25$, and the Chinese remainder theorem doesn't let you split up the power of a prime. $\endgroup$ – Arthur Aug 14 '16 at 16:13
  • $\begingroup$ @Pixar I have added a proof of that. I think modulo 3 and 5 is not strong enough to ensure that the number we find will solve the original question. $\endgroup$ – edm Aug 14 '16 at 16:20
  • $\begingroup$ @Pixar One can also do it without CRT (or Euler), e.g. see my answer. $\endgroup$ – Bill Dubuque Aug 14 '16 at 16:36
  • $\begingroup$ @BillDubuque I've found that reading theory from books is inefficient for my brain, so I am learning by studying particular problems. That is why I am reading all of the answers to the question :) $\endgroup$ – Pixar Aug 14 '16 at 16:46
3
$\begingroup$

If you don't know Euler's theorem or CRT we still can compute it very simply. Notice

${\rm mod}\ 25\!:\,\ 3^{\large 3}\equiv 2\,\Rightarrow\, 3^{\large 9}\equiv 8\,\Rightarrow\, 3^{\large 10}\equiv -1\,\Rightarrow\,\color{#0a0}{3^{\large 20}\equiv 1},\ $ therefore

$$ \color{#90f}{3^{\large 20J-1}}\equiv \dfrac{(\color{#0a0}{3^{\large 20}})^{\large J}}{3}\equiv \dfrac{\color{#0a0}1^{\large J}}3\equiv \dfrac{-24}3\equiv\,\color{#90f}{ -8\!\pmod{25}}\quad\ $$

Therefore $\ 3^{\large 20J+1}\! = 3^{\large 2}(\color{#90f}{3^{\large 20J-1}}) = 9(\color{#90f}{-8+25n}) \equiv -72\pmod{9\cdot 25},\ $ and

$\qquad\quad\ \ \begin{align} {\rm mod}\ 9\!:\,\ 7^{\large 3}\equiv (-2)^{\large 3}\equiv1\\ {\rm mod}\ 25\!:\ 7^{\large 4}\equiv (-1)^{\large 2}\equiv 1\end{align}\,\ $ therefore $\,\ \color{#c00}{7^{\large 12}\equiv 1}\pmod{9\cdot 25}$

Combining yields $\ \ \bbox[10px,border:1px solid black]{3^{\large 20J+1}\! + \color{#c00}7^{\large \color{#c00}{12}K}\!\equiv -72+ \color{#c00}1^{\large K}\equiv -71 \pmod{9\cdot 25}}$

Remark $\ $ OP is a special case since its exponents have above form. Indeed

note $\,\ {\rm mod}\ 20\!:\ 999^{\large 100}\equiv (-1)^{\large 100}\equiv 1\ $ so $\,\ 999^{\large 100}\! = 20J+1,\ $

and $\,\ 12\mid 96\,\Rightarrow\,12\mid 960\,\Rightarrow\,12\mid 960^{\large 961}\ $ so $\,\ 960^{\large 961} = 12K$

$\endgroup$
2
$\begingroup$

Luckily, since $7$ and $225$ are coprime, you can use Euler's Theorem.

We can calcultate that $\phi(225) = 120$.

Thus, $$7^{960^{961}} = 7^{(8\cdot 120)^{961}} = 7^{120\cdot (8^{961}120^{960})}$$$$ = (7^{120})^{ 8^{961}120^{960}} = (7^{\phi(225)})^{ 8^{961}120^{960}} \equiv 1^{ 8^{961}120^{960}} = 1 \mod 225$$

$\endgroup$
  • $\begingroup$ Benguin, can you check the end of my post. I edited, and tried to compute the first expression. Can you tell me if I made mistakes, because I want to learn this? $\endgroup$ – Kamil Aug 14 '16 at 10:54
  • $\begingroup$ I couldn't help but notice that you have $20(50-1)$ which is equal to $980$ and not $999$? $\endgroup$ – benguin Aug 14 '16 at 11:02
1
$\begingroup$

I wrote a tiny python library for computations like this one some days ago. It is based on thinking about finite automata. I don't need the modulus to have any special divisibility properties; the method just demands that it be small enough.

>>> import roll
>>> (roll.mod([3, 999, 100], 225) + roll.mod([7, 960, 961], 225)) % 225
154

My answer agrees with edm's.

The essential part of the library code:

def nat_mod_roll(a, b):
    flat, loop = b
    return a if a < flat else (a - flat) % loop + flat

def roll_of_powers(a, b):
    powers = [1]
    while True:
        c = nat_mod_roll(a*powers[-1], b)
        if c in powers:
            return powers.index(c), len(powers) - powers.index(c)
        powers.append(c)

def tower_mod_roll(a, b):
    if len(a) == 0:
        return nat_mod_roll(1, b)
    return nat_mod_roll(a[0]**tower_mod_roll(a[1:], roll_of_powers(a[0], b)), b)

def mod(a, b):
    if isinstance(a, int): a = a,
    if isinstance(b, int): b = 0, b
    return tower_mod_roll(a, b)

For more explanations see the full code or request them.

$\endgroup$

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.