6

How can I show that $4^{1536} - 9^{4824}$ can be divided by $35$ without remainder?

I'm not even sure how to begin solving this, any hints are welcomed!

$$(4^{1536} - 9^{4824}) \pmod{35} = 0$$

Michael Hardy
  • 1
Ilan Aizelman WS
  • 4,128
  • 1
    Divisibility by $5$ is easy because of $4\equiv 9\equiv -1\mod 5$ – Peter Dec 12 '16 at 18:47
  • For dividibility by $7$, reduce the exponents modulo $6$ (You can also replace $9$ by $2$). It turns out that we get $4^0-2^0=0$, so the number is divisible by $7$ as well. The reduction can be done because of Fermat's little theorem implying $4^6\equiv 2^6\equiv 1\mod 7$ – Peter Dec 12 '16 at 18:48

5 Answers5

4

Euler's theorem implies, since $\varphi(35)=24$, that $$4^{24}\equiv 9^{24}\equiv 1\pmod {35}$$

Since $1536$ and $4824$ are multiples of $24$, the conclusion follows:

$$4^{1536}-9^{4824}=(4^{24})^{64}-(9^{24})^{201}\equiv1^{64}-1^{201}\equiv 0\pmod{35}$$

ajotatxe
  • 65,084
3

Notice that it's divisible iff $5$ and $7$ divide it. Look that

$$4^{1536}-9^{4824}\equiv_5 (-1)^{1536}-(-1)^{4824}= 1-1=0$$

then for the $7$, look that:

$$4^{1536}-9^{4824}\equiv_7 (16)^{768}-(2)^{4824}\equiv_7 (9)^{768}-(8)^{1608}\equiv (2)^{768}-(1)^{1608}$$

But $1^{1608}=1$, and $2^{768}=8^{256}$, so $$(2)^{768}-(1)^{1608}\equiv 8^{256}-1\equiv 1^{256}-1=0$$

For the case of division by $7$, I reduced the modules dividing by $2$ and trying to find a number congruent to $1$. If you use the little Fermat theorem, you could reduce the operations.

iam_agf
  • 5,438
2

Since $35=7*5$ and $5,7$ are prime, it suffices to show that that is divisible by both $5$ and $7$. To do this, note that $4\equiv 9\equiv -1$ mod $5$, so $$ 4^{1536}-9^{4824}\equiv (-1)^{1536}-(-1)^{4824}\equiv 1-1\equiv 0\mod 5. $$ To show divisibility by $7$ requires a bit more work; try to show that successive powers of an element eventually cycle mod $7$, and then you will be able to get a nice form for them.

TomGrubb
  • 12,909
  • For divisbiblity by 7 invoke Fermat little theorem when $a\ne p, a^{p-1} = 1 \pmod p$ for all prime p. – Doug M Dec 12 '16 at 18:52
  • 1
    This too^ I just remember that when I was a beginner with modular arithmetic, it was personally incredibly helpful to actually see the cycling firsthand. But of course if they know these theorems then yes, this is much faster. – TomGrubb Dec 12 '16 at 18:54
2

Note that, for increasing integer values of $n $, the value of $4^n \mod 35$ (let us call it $r_1$) shows a cyclic behaviour. In particular, for any $n \equiv k\mod 6$, we have

$$ k=0\rightarrow r_1 =1$$ $$ k=1\rightarrow r_1 =4$$ $$ k=2\rightarrow r_1 =16$$ $$ k=3\rightarrow r_1 =29$$ $$ k=4\rightarrow r_1 =11$$ $$ k=5\rightarrow r_1 =9$$

Similarly, considering increasing integer values of $n $, the value of $9^n \mod 35$ (let us call it $r_2$) shows the following cyclic behaviour for any $n \equiv k\mod 6$. We have

$$ k=0\rightarrow r_2 =1$$ $$ k=1\rightarrow r_2 =9$$ $$ k=2\rightarrow r_2 =11$$ $$ k=3\rightarrow r_2 =29$$ $$ k=4\rightarrow r_2 =16$$ $$ k=5\rightarrow r_2 =4$$

Now both $1536$ and $4824$ are $\equiv 0\mod 6$, so that both $4^{1536} $ and $9^{4824} $ are $\equiv 1 \mod 35$.

Anatoly
  • 17,079
1

Hint

$4^{1536}-9^{4824} =64^{512}-729^{1608} =(7*9+1)^{512}-(7*104+1)^{1608}≡ 0 \mod 7$

Takahiro Waki
  • 2,310