What is the remainder when 1 n + 2 n + 3 n + … + 99 n is divided by 1 + 2 + 3 + … + 99? My first idea on how to approach was to create a polynomial expansion for the first few terms and then try to find a pattern for the rest but this became cumbersome and I don't think that this is a right approach as this would quickly become a problem that involves factorials and I have not covered modular arithmetic, is there a way to approach this problem in such a way that does not involve using factorials with mods.

Question

What is the remainder when       1    n    +      2    n    +      3    n    +  …  +      99    n   is divided by   1  +  2  +  3  +  …  +  99? My first idea on how to approach was to create a polynomial expansion for the first few terms and then try to find a pattern for the rest but this became cumbersome and I don&#039;t think that this is a right approach as this would quickly become a problem that involves factorials and I have not covered modular arithmetic, is there a way to approach this problem in such a way that does not involve using factorials with mods.

Zoey Benitez · Accepted Answer

Step 1An ad-hoc solution:n odd one can group       1    n    +      99    n    ,      2    n    +      98    n    ,  .  .      .50    n   to get       S    n   divisible by 50 and similarly       1    n    +      98    n    ,  .      .49    n    +      50    n   to get       S    n   divisible by 99 so as noted above the remainder is zero.For n even we notice that modulo 3 each group   3  k  −  2  ,  3  k  −  1  ,  k  =  1  ,  .  .33 gives a sum that is 2 modulo 3 and since there are 33 such sums,       S    n   is then 3 modulo 9 as the multiples of 3 give zero modulo 9 for   n  ≥  2 but there is an odd number of them 15 that are odd so       S    n    =  9  ×  (  2  m  +  1  )  +  qModulo 5 we have to split into   n  =  4  k  +  2 when we have 20 sums that are 0 modulo 5 so Sn is divisible by 25 and then   n  =  4  k when similarly we get       S    n    =  80  =  5 modulo 25 and since       S    n   is always even,       S    n   is 30 modulo 50Modulo 11 we have two cases - n multiple of 10 we get then       S    n    =  90  =  2 modulo 11 (9 sums of 10 each) and n not multiple of 10 when       S    n   is divisble by 11 (easily seen for   n  ≤  8 since       S    n   has a factor of 99 and a denominator that doesn&#039;t contain 11 and then by periodicity since       S    n    =      S          n      +      10       modulo 11)Step 2Putting it together we get:  n  =  2  k  +  1 we get 0  n  =  4  k  +  2  ,  n  ≠  10  m the remainders modulo 50,9,11 are 0,3,0 so we get 1650  n  =  4  k  +  2  ,  n  ≠  10  m the remainders modulo 50,9,11 are 30,3,0 so we get 3630  n  =  20  k  +  10 the remainders modulo 50,9,11 are 0,3,2 so we get 750  n  =  20  k the remainders modulo 50,9,11 are 30,3,2 so we get 2730 and that&#039;s all!

kituoti126 · Accepted Answer

Step 1  We have        ∑          x      =      1        n        x    2    =            n      (      n      +      1      )      (      2      n      +      1      )        6      and        ∑          x      =      1        n    x  =            n      (      n      +      1      )        2    If we divide the first by the second, we can readily see terms cancel so                      ∑                  x          =          1                n                    x        2                            ∑                  x          =          1                n            x        =            (      2      n      +      1      )        3  Plugging in the value 99 we get  R  =  2  n  +  1    mod      3    ⟹        199    3    =  66     R  1  For cubes we have        ∑          x      =      1        n        x    3    =                    n        2            (      n      +      1              )        2              4      ⟹    R  =  n  (  n  +  1  )    mod      2      ⟹        9900    2    =  4950     R  0Sums of odd powers are divisible by             n      (      n      +      1      )        2  Sums of even powers are divisible by            n      (      n      +      1      )      (      2      n      +      1      )        6    =            n      (      n      +      1      )        2    ×            2      n      +      1        3    Step 2I have in the past worked out summation formulas for powers up to       x          31       the process is tedious and I would have trouble locating them right now. I could have gone farther but for lack of arbitrary precision. Any formula can be generated with a set of simultaneous equations represented in matrix form where the coefficients come from a modified Pascal&#039;s triangle or the formula&#039;s may be generated directly with selected Bernoulli numbers but that is beyond the scope of this question, Here is one more sample what we are looking for.      ∑          x      =      1        n        x    4    =            n      (      n      +      1      )        2    ⋅            (      2      n      +      1      )      (      3              n        2            +      3      n      −      2      )        15      ⟹    R  =  (  2  n  +  1  )  (  3      n    2    +  3  n  −  2  )  )    mod      15    ⟹        5909902    15    =  393993     R  7I disagree with the sequence suggested by one of the comments because it appears that, for       x    2    ,  R  =  1 and for       x    3    ,  R  =  0 and for       x    4    ,  R  =  7 (do check my math)

What is the remainder when 1^n+2^n+3^n+…+99^n is divided by 1+2+3+…+99?

Answered question

Answer & Explanation

New Questions in Algebra II