Di-topical problem

Number Theory Level 4

Find the remainder when $6^{ 2015 }+8^{ 2015 }$ is divided by 49.

The answer is 35.

4 solutions

Discussions for this problem are now closed

Nick Lee
Jan 25, 2015

Notice that $6^{ 2015 }=(7-1)^{ 2015 }={ _{ 2015 }{ C }_{ 2015 } }7^{ 2015 }-{ _{ 2015 }{ C }_{ 2014 } }7^{ 2014 }+\cdots -{ _{ 2015 }{ C }_{ 1 } }7^{ 1 }+{ _{ 2015 }{ C }_{ 0 } }7^{ 0 }$

We only have to worry about the last 2 terms since the rest of the terms are divisible by 49.

Similarly, $8^{ 2015 }=(7+1)^{ 2015 }={ _{ 2015 }{ C }_{ 2015 } }7^{ 2015 }+{ _{ 2015 }{ C }_{ 2014 } }7^{ 2014 }+\cdots +{ _{ 2015 }{ C }_{ 1 } }7^{ 1 }+{ _{ 2015 }{ C }_{ 0 } }7^{ 0 }$

Here, we only have to worry about the last 2 terms.

$\therefore { 6 }^{ 2015 }+{ 8 }^{ 2015 }\equiv ({ 7 }^{ 1 }{ _{ 2015 }{ C }_{ 1 } }-{ 7 }^{ 0 }{ _{ 2015 }{ C }_{ 0 } })+({ 7 }^{ 1 }{ _{ 2015 }{ C }_{ 1 } }+{ 7 }^{ 0 }{ _{ 2015 }{ C }_{ 0 } })\quad (mod\quad 49)\\ \equiv 7(2015)+7(2015)\quad (mod\quad 49)\equiv 35\quad (mod\quad 49)$

(I skipped the last part of the calculation...)

Is there a solution which someone studying in 9th standard understand??

Aarabdh Tiwari - 6 years, 4 months ago

You just need to know a little bit of modular arithmetic and its properties, then the answer will be immediate.

Otherwise, you can note the remainders of both the numbers $6^n$ and $8^n$ have a cycle of $42$ , that means every time $n$ is increased by $42$ , the remainder is still the same, so we just need to find the remainder of $2015$ when divided by $42$ , which yields $41$ . Then refer back to your calculated values of remainder for $n=1,2,3,4,5, \ldots, 42$ , you will get the answer. But this is still plenty of tedious work.

You can either learn Nick's solution which applies Binomial Expansion and cuts off almost all the terms thus removing plenty of calculation. Or learn an extra step in modular arithmetic called Euler's Theorem which greatly simplifies your working. Or you could just learn basics of modular arithmetic without Euler's Theorem, and you will figure out how to find the remainder, still a little bit tedious and you need patience to work on it, but it's definitely a huge short cut if you don't learn modular arithmetic.

Pi Han Goh - 6 years, 2 months ago

Daniel Liu
Jan 26, 2015

Note that $6^{\phi(49)}=6^{42}\equiv 1\pmod{49}$ and $8^{\phi(49)}=8^{42}\equiv 1\pmod{49}$

Thus, $6^{2015}+8^{2015} = 6^{-1+42\cdot 48}+8^{-1+42\cdot 48}\equiv 6^{-1}+8^{-1}\pmod{7}$

However, $6^{-1}\equiv 41\pmod{49}$ and $8^{-1}\equiv 43\pmod{49}$

Thus, $6^{-1}+8^{-1}\equiv 41+43\equiv \boxed{35}\pmod{7}$

Alexandre Miquilino
Jan 27, 2015

Let's rewrite this sum:

$6^{2015} + 8^{2015} = (7 - 1)^{2015} + (7 + 1)^{2015}$

$= \sum_{i=0}^{2015}{2015 \choose i}7^{i}*(-1)^{2015-i} + \sum_{j=0}^{2015}{2015 \choose j}7^{j}$

Notice that for every $i \geq 2$ , as well as for every $j \geq 2$ , the corresponding terms of the sum will be divisible by $49$ since it's equal to $7^{2}$ .

Thus, we can write:

$\sum_{i=0}^{2015}{2015 \choose i}7^{i}*(-1)^{2015-i} + \sum_{j=0}^{2015}{2015 \choose j}7^{j} \equiv$

$(-1)^{2015} + 2015*7 + 1 + 2015*7 \pmod{49}$

The $RHS$ of the equation equals $28210$ ; this number, divided by $49$ , yields a remainder of $35$ , which is the sought solution.

Ameya Patil
Jan 28, 2015

use fermet's theorem......... 6^2015 can be written as 6^(42*6 -1) divided by 49...... 42 is the euler's number of 49 ... and 6 and 49 are the coprimes of each other so the remainder is 1..... rest for the other part of the dividend that is 6^-1 divided by 49..... so, remainder 1 can be written as -48 divided by 49 and multiply it with 6^-1 divided by 49.... by remainder theorem the answer is -8 ..... do the same for the 8^2015 term and u will get the remainder as -6..... so the total remainder is -14.... add to 49.... the even remainder is 35.... hahahaha

Di-topical problem

The answer is 35.

4 solutions

Discussions for this problem are now closed

0 pending reports