Finding the mod of a difference of large powers

Question

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.

Answer 1

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.

Answer 2

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$.

Answer 3

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$.

Answer 4

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.

Answer 5

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$.

Answer 6

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}$