Waste less time on Facebook — follow Brilliant.
×

Number Theory Question

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

Note by Sangeeta Mishra
4 years, 6 months ago

No vote yet
6 votes

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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} \)

Comments

Sort by:

Top Newest

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.

Aditya Parson - 4 years, 6 months ago

Log in to reply

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}\)

Bob Krueger - 4 years, 6 months ago

Log in to reply

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

Jeffer Dave Cagubcob - 4 years, 6 months ago

Log in to reply

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)

Lab Bhattacharjee - 4 years, 6 months ago

Log in to reply

\[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

Lab Bhattacharjee - 4 years, 6 months ago

Log in to reply

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.

Calvin Lin Staff - 4 years, 6 months ago

Log in to reply

There's a formatting error in your second equation.

Tim Vermeulen - 4 years, 6 months ago

Log in to reply

ya

Vamsi Krishna Appili - 4 years, 6 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...