Number Theory Question

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

Note by Sangeeta Mishra
8 years ago

No vote yet
6 votes

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai−1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 ∑i=13 \sum_{i=1}^3
\sin \theta sin⁡θ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Let the remainder when 1313 divides 21052^{105} be cc and when it divides 31053^{105} be dd.

We can write it as:

2105≡c(mod13)2^{105} \equiv c \pmod{13} and 3105≡d(mod13)3^{105} \equiv d \pmod{13}

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

1∗(29)≡c(mod13) 1*(2^{9}) \equiv c \pmod{13} and 1∗(39)≡d(mod13) 1*(3^{9}) \equiv d \pmod{13}

2∗(162)≡c(mod13) 2*(16^{2}) \equiv c \pmod{13} and 3∗(812)≡d(mod13) 3*(81^{2}) \equiv d \pmod{13}

2∗(32)≡c(mod13) 2*(3^{2}) \equiv c \pmod{13} and 3∗(32)≡d(mod13) 3*(3^{2}) \equiv d \pmod{13}

Hence, 2105≡5(mod13)2^{105} \equiv 5 \pmod{13} and 3105≡1(mod13)3^{105} \equiv 1 \pmod{13}

Therefore,

2105+3105≡6(mod13)2^{105} + 3^{105} \equiv 6 \pmod{13}

That is the given expression is not divisible by 1313, since it leaves behind a remainder of 66.

Hence proved.

Aditya Parson - 8 years 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, ap≡amod  pa^p \equiv a \mod{p}. Using this, 2105≡2⋅(213)8≡2⋅28≡29(mod13)2^{105} \equiv 2 \cdot \left( 2^{13} \right) ^8 \equiv 2 \cdot 2^8 \equiv 2^9 \pmod{13}

Bob Krueger - 8 years ago

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

Jeffer Dave Cagubcob - 8 years ago

Another approach is to observe that 13=22+32 13 = 2^2 + 3^2 . Hence, this tells us that 2105+3105=(22+32)(2103)−210332+3105 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

2105+3105=(22+32)×Q+2×3104+3105=13Q+5×3104 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 −22≡32(mod13)-2^2 \equiv 3^2 \pmod{13} , hence 2104≡3104(mod13) 2^{104} \equiv 3^{104} \pmod{13} . As such, 2105+3105≡21×3104+3105≡5×3104(mod13) 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 - 8 years ago

Log in to reply

There's a formatting error in your second equation.

Tim Vermeulen - 8 years ago

Log in to reply

ya

Vamsi Krishna Appili - 8 years ago

22n+1+32n+1=2⋅4n+3⋅9n=2⋅4n+3(13−4)n≡4n(2+3(−1)n)(mod13)≢02^{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 22n+32n=4n+9n=4n+(13−4)n≡4n(1+(−1)n)(mod13)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 - 8 years ago

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

So, 2n+3n2^n+3^n will be divisible by 13 iff 8n≡−1(mod13)8^n\equiv-1\pmod{13}

Now, as 82=64≡−1(mod13)  ⟹  82(2m+1)≡−18^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 - 8 years ago
×

Problem Loading...

Note Loading...

Set Loading...