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

No vote yet
6 votes

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

Log in to reply

@Aditya Parson 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, 1 month ago

Log in to reply

@Aditya Parson your proving is wrong... XD ... it needs a BOX.. Jeffer Dave Cagubcob · 4 years, 1 month 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, 1 month 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, 1 month 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, 1 month ago

Log in to reply

@Calvin Lin There's a formatting error in your second equation. Tim Vermeulen · 4 years, 1 month ago

Log in to reply

@Tim Vermeulen ya Vamsi Krishna Appili · 4 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...