I am learning from chapter 1 of the algorithm textbook known as DPV.

There is a question 1.11 that asks:

Is $4^{1536} - 9^{4824}$ divisible by 35?

The whole chapter is on modular arithmetic, modular exponentiation, Euclid GCD (as far I got so far) so I broke down the first term to

$2^{3072}$ and second term to

$3^{2(2048)} * 3^{2(2048)} * 3^{3(512)} * 3^{2(128)} * 3^{3(64)} * 3^{3(16)} * 3^{3(8)}$ thinking it would lead to some sort of aha moment but the only conclusions I can draw is that the first term's factors are all divisible by 2, the second term's are all divisible by 3 and 35 has factors 5 and 7 so neither is divisible by 35 on its own. How can I apply any of the modular arithmetic or Euclid's GCD to this problem to solve it?

  • 1
    $\begingroup$ Note first that $4\equiv 9\mod 5$, so there is a conclusion to be drawn from that. Next you have already changed $4^k$ into $2^{2k}$ so consider either using $9\equiv 2\mod 7$ or else $4\equiv -3\mod 7$ and $9^k=3^{2k}$... $\endgroup$ – abiessu 2 days ago
  • 2
    $\begingroup$ Without going as far as which theorems to use, note that if you find out $4^{1536}\equiv x$ and $9^{4824}\equiv y \bmod 35$ then the divisibility question is whether $x \equiv y \bmod 35$. $\endgroup$ – Joffan 2 days ago
  • 1
    $\begingroup$ The place to start is to identify the smallest positive integers $a,b,r,s$ where $4^a \equiv 1\pmod{5}, 9^r \equiv 1\pmod{5}, 4^b \equiv 1\pmod{7},$ and $9^s \equiv 1\pmod{7}.$ Note that if (for example) $4^a \equiv 1\pmod{5}$ and $4^b \equiv 1\pmod{7}$ and if (also) $c$ is any common multiple of both $a$ and $b$, then $4^c \equiv 1\pmod{35}.$ Once a value $c$ is identified, then you know that for any positive integer $k, ~4^{(kc)}\equiv 1\pmod{35}.$ Therefore, you would then consider what the least non-negative residue of $(1536)$ is $\pmod{c}.$ $\endgroup$ – user2661923 2 days ago

Note that if $4^{1536}\equiv 9^{4824} \bmod 35$ then $35$ divides $4^{1536}- 9^{4824}$, otherwise not.

There are various tools that could help you decide this, and if you have heard of Euler's theorem and the Chinese remainder theorem these could certainly help, but with just the idea of modular exponentiation you can investigate the powers of $4$ and $9$ $\bmod 35$ and reach a conclusion.

Successive powers of $4\bmod 35$ look like: $4^1 \equiv \color{blue}{4}, 4^2\equiv \color{blue}{16}, 4^3\equiv 64\equiv \color{blue}{29}, 4^4\equiv 116\equiv \color{blue}{11}, 4^5\equiv 44\equiv \color{blue}{9}, 4^6\equiv 36\equiv \color{red}{1}$

Successive powers of $9\bmod 35$ look like: $9^1 \equiv \color{blue}{9}, 9^2\equiv 81\equiv \color{blue}{11}, 9^3\equiv 99\equiv \color{blue}{29} 9^4\equiv 261\equiv \color{blue}{16}, 9^5\equiv 144\equiv \color{blue}{4}, 9^6\equiv 36\equiv \color{red}{1}$

(If you know about modular inverse, you can also see from the powers of $4$ that $4^{-1}\equiv 9 \bmod 35$ which is why the two power value sequences are mirror images of each other.)

And then casting out multiples of $6$ in the exponent allows us to finish the calculations without difficulty; for example $4^{23} = 4^{3\cdot\color{red}{6}+\color{blue}{5}}\equiv \color{red}{1}^3\cdot 4^{\color{blue}{5}}\equiv \color{red}{1}\cdot \color{blue}{9}\equiv 9\bmod 35$.


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.