# Number Theory Question

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

Note by Sangeeta Mishra
5 years, 1 month ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

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.

- 5 years, 1 month 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}$$

- 5 years, 1 month ago

your proving is wrong... XD ... it needs a BOX..

- 5 years, 1 month 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)

- 5 years, 1 month 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

- 5 years, 1 month 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 - 5 years, 1 month ago

There's a formatting error in your second equation.

- 5 years, 1 month ago

ya

- 5 years, 1 month ago