# Finding the mod of a difference of large powers

I am trying to find if $$4^{1536} - 9^{4824}$$

is divisible by 35. I tried to show that it is not by finding that neither power is divisible by 35 but that doesn't entirely help me. I just know that I can't use fermats little theorem to help solve it.

• It doesn't help, because both are clearly not divisible by 35. Just find if the two powers have the same residue mod 35 – Old John Feb 13 '15 at 23:40
• It's definitely divisible by $5$ as its last digit is $5$ (check last digits of $4^n$ and $9^n$. Perhaps this might be useful (so you need to check divisibility by $7$). – Andrei Rykhalski Feb 13 '15 at 23:41
• @AndreiRykhalski: $4^4-9^1=247$ is not divisible by $5$. – barak manos Feb 13 '15 at 23:45
• @barakmanos I didn't mean that $4^n$ - $9^m$ for all $n$ and $m$, but the fact that last digit of a power of a number is a periodic function. – Andrei Rykhalski Feb 13 '15 at 23:48

First, $$4^{1536}-9^{4824}\equiv(-1)^{1536}-(-1)^{4824}\equiv 1-1\equiv 0\pmod{5}.$$ Second, $$4^{1536}-9^{4824}=64^{512}-729^{1608}\equiv 1^{512}-1^{1608}\equiv 1-1\equiv 0\pmod{7}.$$

Edit: if you are unfamiliar with modular arithmetic, think in terms the Binomial Theorem. For example, (below, $A$ is some integer) $$4^{1536}=(5-1)^{1536}=5A+(-1)^{1536}=5A+1$$ where the last equality follows because $1536$ is even.

• How does 4 turn into -1? – user138246 Feb 13 '15 at 23:57
• $4\equiv-1\pmod{5}$ because $4-(-1)=5$ is divisible by $5$. – yurnero Feb 13 '15 at 23:58
• I don't follow that logic, can you demonstrate with a more simple example? – user138246 Feb 14 '15 at 0:16
• I don't know the binomial theorem either but how is it that you are taking the powers of 4 and 9 and turning them both into 1? – user138246 Feb 14 '15 at 0:28
• @user138246 $a\equiv b\pmod{p}\implies a^n\equiv b^n\pmod{p}, \forall n\in\mathbb N$, because $a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^2+\cdots+ab^{n-2}+b^{n-1})$, so $4\equiv -1\pmod{5}\implies 4^{1536}\equiv (-1)^{1536}\equiv 1\pmod{5}$, because $(-1)^{1536}=1$. Same logic for everything else. – user26486 Feb 14 '15 at 0:38

Note $4^6\equiv (-6)^2 \equiv 1$ (mod $35$) and $6 \mid 1536$, so $4^{1536}\equiv 1$ (mod $35$).

Similarly $9^6 \equiv 1$ (mod $35$) $\implies 9^{4824}\equiv 1$ (mod $35$).

So we can conclude that $4^{1536}-9^{4824} \equiv 0$ (mod $35$), i.e. the number is divisible by $35$.

• I don't understand the $6 | 1536$ part, what does that mean? – user138246 Feb 14 '15 at 0:19
• @user138246 $6\mid 1536\implies 1536=6c$ for some $c\in\mathbb N$, so $4^{1536}\equiv 4^{6\cdot c}\equiv (4^6)^c\equiv 1^c\equiv 1\pmod{35}$. We had $(4^6)^c\equiv 1^c\pmod{p}$ because $4^6\equiv 1\pmod{p}$ and $a\equiv b\pmod{p}\implies a^n\equiv b^n\pmod{p},\forall n\in\mathbb N$, because $a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+\cdots+ab^{n-2}+b^{n-1})$. – user26486 Feb 14 '15 at 0:43

Hint mod $\,5\!:\ 4\equiv -1\equiv 9\,\Rightarrow\, \color{#c00}{4^6\equiv 1\equiv 9^6}$

and,  mod $\,7\!:\ 9^3\equiv 2^3\equiv 1\,\Rightarrow\ \color{#c00}{4^6\equiv 1\equiv 9^6}$

So mod $\,35\!:\ \color{#c00}{4^3\equiv 1\equiv 9^3}\$ by CRT  (or by $\,5,7\mid a^6\!-\!1\,\Rightarrow\,{\rm lcm}(5,7)=35\mid a^6\!-\!1)$

So mod $\,35\!:\ \color{#c00}4^{\color{#c00}3j} - \color{#c00}9^{\color{#c00}9^k}\equiv \color{#c00}1^{j}-\color{#c00}1^{k} \equiv 1$

In particular it's true if the exponents are even with digit sum divisible by $\,3,\,$ as in your case.

Remark $\$ Since you say congruence arithmetic is unfamiliar, below is a more elementary proof using only that $\,a-b\mid a^n-b^n.\$ Suppose $\ 2\mid j\!-\!i \ge 0.\$ Then

\qquad\quad \begin{align} 9^{3j}-4^{3i} = &\ 9^{3j}-4^{3j}\ +\ 4^{3j}-4^{3i}\\ = &\ \color{#0a0}{9^{3j}-4^{3j}}\ +\ 4^{3i}\,(\color{#c00}{4^{3(j-i)}\!-1})\end{align}

But $\ 5,7\mid 9^3-4^3\mid \color{#0a0}{9^{3j}-4^{3j}}$ and $\,5,7\mid 4^6-1\mid \color{#c00}{4^{3(j-i)}\!-1}\,$ by $\,2\mid j\!-\!i\,\Rightarrow\, 6\mid 3(j\!-\!i)$

Thus $\,5,7\,$ also divide their sum, therefore their lcm = $\,5\cdot 7 = 35\,$ divides their sum.

• Can you explain your notation, I am not familiar with it enough to read this commit. I don't know what the : implies, I don't know what CRT is, I don't know what lcm is either. Thanks. – user138246 Feb 14 '15 at 0:15
• @user138246 Do you know congruence arithmetic? i.e. $\,a\equiv b\pmod m\$ iff $\ m\mid a-b\ \$ – Gone Feb 14 '15 at 0:21
• I do not and I do not know what | means – user138246 Feb 14 '15 at 0:22
• @user138246 Usually these problems are posed after one learns a bit of elementary number theory. You should state in your question that you are not familiar with congruences or modular arithmetic. What textbook are you using? – Gone Feb 14 '15 at 0:29
• I know a little bit of modular arithmetic and the idea of congruence, I am just not familiar with the math heavy notation and acronyms. – user138246 Feb 14 '15 at 0:30

Fermat's little theorem:

"If $p$ is a prime number, then: $\forall$ $x \in \Bbb N / gcd(x,p) = 1$, $x^{p-1} \equiv 1 \pmod p$".

Let $N = 4^{1536} - 9^{4824}$.

$4^{1536} = (4^6)^{256} \equiv 1 \pmod 7$ (Fermat's little)

$9^{4824} = (9^6)^{804} \equiv 1 \pmod 7$ (Again, Fermat)

Thus: $N \equiv 1 - 1 \pmod 7 \equiv 0 \pmod 7$. This shows that $7 | N$.

Now:

$4^{1536} = (4^4)^{384} \equiv 1 \pmod 5$ (Fermat..)

$9^{4824} = (9^4)^{1206} \equiv 1 \pmod 5$ (Again)

Thus: $N \equiv 1 - 1 \pmod 5 \equiv 0 \pmod 5$.

This shows $5|N$.

Therefore $5|N$ and $7|N$. This gives $35|N$.

• Why is $4^{6*256} = 1 (mod 7)$ I don't follow. 1 mod 7 is just 1 but how did you conclude that 4 raised to some massive power is equal to 1? It makes no sense to me. – user138246 Feb 13 '15 at 23:59
• $4^6 \equiv 1 \pmod 7$ using the aforementioned theorem. Now raise both sides to that "massive power". $1$ will still be $1$. – user207710 Feb 14 '15 at 0:01
• Yes I see that but you are making the claim that some number (that is not 1) is equal to 1. I do not see how that stands. – user138246 Feb 14 '15 at 0:04
• "$a \equiv b \pmod n$" means that the remainder of division of $a$ by $n$ is $b$. It doesn't mean that $a = b$. – user207710 Feb 14 '15 at 0:08
• Was the "I can't use Fermat" bit present from the beginning? I completely missed that. – user207710 Feb 14 '15 at 0:11

I have little background in this area, but I can determine the answer, ergo anyone else with little background should have no trouble following along.

I know that $x^n$ mod $p$ will follow a cyclic pattern as n is iterated, so I'll first find what those cycles are for $4^n$ mod $35$ and $9^n$ mod $35$, for $n = 0,1,2,3...$

$4^n$ mod $35 = 1,4,16,29,11,9,1,4,16,29...$

$9^n$ mod $35 = 1,9,11,29,16,4,1,9,11,29...$

So we see that both cycles have a length of 6, so you can know what each number's $nth$ power mod $35$ is by what the exponent $n$ mod $6$ is. $4^a - 9^b$ will be divisible by $35$ if $4^a$ and $9^b$ have the same value mod $35$. Importantly, the two cycles above are in fact the reverse of each other. So $4^a$ will have the same value mod $35$ as $9^b$ if $a$ mod $6 = (6 - (b$ mod $6))$ mod $6$. As it happens, both $1536$ mod $6$ and $4824$ mod $6$ equal $0$, so they do satisfy the aforementioned equation, and therefore $4^{1536} - 9^{4824}$ IS divisible by $35$.

I will suggest to use Euler's Theorem which states $\forall a \in \mathbb{Z}$ s.t. gcd$(a, n)=1$, then $a^{\phi(n)} \equiv 1$ mod $n$

In your case we have $n=35$, $\quad a=4,9\quad$ and $\quad \phi(35)=24$

So $\quad \quad 4^{24} \equiv 1$ mod $35\quad$ and $\quad 9^{24} \equiv 1$ mod $35\quad$

Since $\quad4$x$64 = 1536 \quad$ and $\quad 9$x$201 = 4824$

So $\quad \quad 4^{1536} \equiv 1$ mod $35\quad$ and $\quad 9^{4824} \equiv 1$ mod $35\quad$

Hence $\quad 4^{1536} - 9^{4824} \equiv 1 - 1 \equiv 0$ mod $35\quad \implies 35 | 4^{1536} - 9^{4824}$