4
$\begingroup$

What is the remainder when $1^6 + 2^6 + 3^6 + ... + 99^6 + 100^6$ is divided by 5?

I think that the only way to solve this would be to applying to the proposition that “the sum/product of congruence classes is equal to the congruence class of the sum/product", however I am unsure how to apply this properly, any suggestions?

$\endgroup$
0

4 Answers 4

6
$\begingroup$

$$1^6+2^6+3^6+4^6+5^6+\dots+100^6\equiv20(1^6+2^6+3^6+4^6+5^6)\\\equiv0\text{ (mod }5)$$

The first conguruence can be applied since $1\equiv6\equiv11\equiv\dots\equiv96\text{ (mod }5)$, $1^6\equiv6^6\equiv11^6\equiv\dots\equiv96^6\text{ (mod }5)$

Likewise, $2^6\equiv7^6\equiv12^6\equiv\dots\equiv97^6\text{ (mod }5)$, and the same can be done with the numbers which are congruent to 3, 4 and 0 modulo 5.

Hence, we can replace all these terms with $1^6+2^6+3^6+4^6+5^6$ repeated 20 times and therefore the sum is a multiple of 20 and is divisible by 5 exactly. (Comment made by David K.)

$\endgroup$
0
5
$\begingroup$

Intuitive Solution

The remainder is $\color{blue}{zero}$.

The numbers, $5^6, 10^6, 15^6, \ldots$ are all divisible by 5.

The rest you can pair up as $(5m \pm 1)^6$ which leaves a remainder $1$ and $(5m \pm 2)^6$ which leave a remainder $-1$, so everything cancels out and we get zero.

$\endgroup$
2
  • 1
    $\begingroup$ This is a fantastic approach. $\endgroup$ Nov 19, 2015 at 3:31
  • $\begingroup$ @VelvetUndergrad Thanks for the appreciative comment. I wonder sometimes why people get lost in symbols and theorems. $\endgroup$
    – Shailesh
    Nov 19, 2015 at 3:32
2
$\begingroup$

Define for $n\in N$ $$t_n=n^6$$ and $$s_n=\sum_{k=0}^{n}t_k$$ Notice that the first differences between the terms of $S=\{s_0, s_1,\dots\}$ are elements of the set $T=\{t_1,t_2,\dots\}$, which, being a subset of $f(x)=x^6$, have constant 6th differences. This implies that $s_n$ is a subset of a 7th degree polynomial, i.e. $$s_n = a_0+a_1n+a_2n^2+a_3n^3+a_4n^4+a_5n^5+a_6n^6+a_7n^7$$ Given that $s_0=0^6=0$ we have $$s_n = a_1n+a_2n^2+a_3n^3+a_4n^4+a_5n^5+a_6n^6+a_7n^7$$ $$s_n = n(a_1+a_2n+a_3n^2+a_4n^3+a_5n^4+a_6n^5+a_7n^6)$$

So obviously $n\mid s_n \implies 100\mid s_{100}$, but $5\mid 100 \implies 5\mid s_{100}\implies s_{100}\equiv 0(\mod 5)$

$\endgroup$
1
  • $\begingroup$ Interesting approach. +1 $\endgroup$
    – Shailesh
    Feb 12, 2016 at 8:58
1
$\begingroup$

We have $p=5$ is prime, then by Fermat's little theorem: for every integer $a$ such that $p \nmid a$ we have $$ a^{p-1} \equiv 1 \mod{p}$$ Now for any $x$ integer in $[1,100]$, if $5$ divides $x$ then the remainder is zero, if $5\nmid x$ , then $x^{4} \equiv 1 \mod{5}$, and so as $$y=1^6+ 2^6+3^6+...+99^6+100^6 = 1^4\cdot1^2+2^4\cdot2^2+3^4\cdot3^2+...+99^4\cdot99^2+100^4\cdot100^2 $$ then $$ y \equiv 1^2+ 2^2+3^2+4^2+6^2+...+99^2 $$ Now for any integer $x$, such that $5\nmid x$, we have $x^2 \equiv \pm 1 \mod{5}$. More precisely, if $ x \equiv 2,3 \mod{5}$ then $x^2 \equiv -1 \mod{5}$, and if $ x \equiv 1,4 \mod{5}$ then $x^2 \equiv 1 \mod{5}$. Thus summing the squares of any four consecutive numbers will be congruent to zero $\mod{5}$.

Hence summing the squares from $1$ to $99$, the remainder would be zero.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .