×

# Number Theory Question

Show that 2^105 + 3^105 is not divisible by 13.

Note by Sangeeta Mishra
3 years, 7 months ago

Sort by:

Let the remainder when $$13$$ divides $$2^{105}$$ be $$c$$ and when it divides $$3^{105}$$ be $$d$$.

We can write it as:

$$2^{105} \equiv c \pmod{13}$$ and $$3^{105} \equiv d \pmod{13}$$

Since $$13$$ is prime, by Fermat's little theorem we can re-write the congruence's as:

$$1*(2^{9}) \equiv c \pmod{13}$$ and $$1*(3^{9}) \equiv d \pmod{13}$$

$$2*(16^{2}) \equiv c \pmod{13}$$ and $$3*(81^{2}) \equiv d \pmod{13}$$

$$2*(3^{2}) \equiv c \pmod{13}$$ and $$3*(3^{2}) \equiv d \pmod{13}$$

Hence, $$2^{105} \equiv 5 \pmod{13}$$ and $$3^{105} \equiv 1 \pmod{13}$$

Therefore,

$$2^{105} + 3^{105} \equiv 6 \pmod{13}$$

That is the given expression is not divisible by $$13$$, since it leaves behind a remainder of $$6$$.

Hence proved. · 3 years, 7 months ago

For those who don't know, here's a bit of a clarification. Fermat's little theorem states that for any positive number a and prime p, $$a^p \equiv a \mod{p}$$. Using this, $$2^{105} \equiv 2 \cdot \left( 2^{13} \right) ^8 \equiv 2 \cdot 2^8 \equiv 2^9 \pmod{13}$$ · 3 years, 7 months ago

your proving is wrong... XD ... it needs a BOX.. · 3 years, 7 months ago

As $2^4\equiv3\pmod {13}, 2^n+3^n\equiv 2^n+2^{4n}\pmod{13}\equiv 2^n(8^n+1)$

So, $2^n+3^n$ will be divisible by 13 iff $8^n\equiv-1\pmod{13}$

Now, as $8^2=64\equiv-1\pmod{13}\implies 8^{2(2m+1)}\equiv-1$ for any non-negative integer m

So, n must be of the form 2(2m+1) where m is any non-negative integer

Now, 105 is not of the form 2(2m+1) · 3 years, 7 months ago

$2^{2n+1}+3^{2n+1}=2\cdot 4^n+3\cdot 9^n=2\cdot 4^n+3(13-4)^n\equiv 4^n\left( 2+3(-1)^n\right)\pmod {13} \not\equiv0$ for any positive integer n

whereas $2^{2n}+3^{2n}=4^n+9^n=4^n+(13-4)^n\equiv 4^n\left( 1+(-1)^n\right)\pmod {13}$ which will be divisible by 13 iff n(>0) is odd · 3 years, 7 months ago

Another approach is to observe that $$13 = 2^2 + 3^2$$. Hence, this tells us that $$2^{105 } + 3^{105} = (2^2 + 3^2) ( 2^{103} ) - 2^{103} 3^2 + 3^{105}$$. Continue to factor out 13 in this way, and you can show that

$2^{105} + 3^{105} = (2^2 + 3^2) \times Q + 2 \times 3^{104} + 3 ^{105} = 13Q + 5 \times 3^{104}$

Hence, this number is not divisible by 13.

In the language of modular arithmetic, we can say that since $$-2^2 \equiv 3^2 \pmod{13}$$, hence $$2^{104} \equiv 3^{104} \pmod{13}$$. As such, $$2^{105 } + 3^{105} \equiv 2^1 \times 3^{104} + 3^{105} \equiv 5 \times 3^{104} \pmod{13}$$, which is not divisible by 13. Staff · 3 years, 7 months ago

There's a formatting error in your second equation. · 3 years, 7 months ago