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$
9
  • $\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
    Commented Aug 14, 2016 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
    Commented Aug 14, 2016 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
    Commented Aug 14, 2016 at 10:07
  • $\begingroup$ But $3$ and $225$ are not coprime. $\endgroup$
    – Kamil
    Commented Aug 14, 2016 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
    Commented Aug 14, 2016 at 10:20

5 Answers 5

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$
6
  • $\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$ Commented Aug 14, 2016 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
    Commented Aug 14, 2016 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
    Commented Aug 14, 2016 at 16:20
  • $\begingroup$ @Pixar One can also do it without CRT (or Euler), e.g. see my answer. $\endgroup$ Commented Aug 14, 2016 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$ Commented Aug 14, 2016 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$
0
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$
4
  • 1
    $\begingroup$ You must have a sign error somewhere since my answer shows that $\,x\equiv -72\pmod{225}\,$ is correct $\ $ $\endgroup$ Commented Aug 14, 2016 at 16:34
  • $\begingroup$ The glitch is in the Bézout relation. $\endgroup$
    – quid
    Commented Aug 14, 2016 at 16:37
  • $\begingroup$ @quid: Oh yes. Is hould have checked my computations. Thanks! $\endgroup$
    – Bernard
    Commented Aug 14, 2016 at 17:11
  • $\begingroup$ @Bill Dubuque: quid found out the error. Fixed. Thanks for pointing it! $\endgroup$
    – Bernard
    Commented Aug 14, 2016 at 17:13
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$
2
  • $\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
    Commented Aug 14, 2016 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
    Commented Aug 14, 2016 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .