6
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Divisibility by $5$ is easy because of $4\equiv 9\equiv -1\mod 5$ $\endgroup$ – Peter Dec 12 '16 at 18:47
  • $\begingroup$ 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$ $\endgroup$ – Peter Dec 12 '16 at 18:48
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ For divisbiblity by 7 invoke Fermat little theorem when $a\ne p, a^{p-1} = 1 \pmod p$ for all prime p. $\endgroup$ – Doug M Dec 12 '16 at 18:52
  • 1
    $\begingroup$ 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. $\endgroup$ – TomGrubb Dec 12 '16 at 18:54
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

Hint

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

$\endgroup$

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.