Re: Any quick way to find a remainder ?

From: Christian Bau (christian.bau_at_cbau.freeserve.co.uk)
Date: 06/02/04 

Date: Wed, 02 Jun 2004 09:00:11 +0100

In article <750cb8c.0406012301.76b29117@posting.google.com>,
 fw_ho@hotmail.com (Andrew) wrote:

> I have a problem from a friend, i want to know the solution.
>
> What is the remainder if the following numver x is divided by 13.
>
> x = 1^2001 + 2^2001 + 3^2001 + .... + 2001^2001
>
> Any help would be appreciated.

Take for example the remainder of (1307^2001) divided by 13.

You get the same result if you take first the remainder of 1307 / 13,
that is 7. So you calculate 7^2001 divided by 13.

Make a table:

   7^1 divided by 13, remainder is 7.
   7^2 divided by 13 = 49/13 = 3 remainder 10.
   7^3 divided by 13 = (10 * 7) / 13 = 70/13 = 5 remainder 5.
   7^4 divided by 13 = (5 * 7) / 13 = 35/13 = 2 remainder 9

and so on. You will see a pattern. Once you spot the pattern, the
remainder of 7^2001 divided by 13 is easy. Do the same for 0, 1, 2 to
12.

Of the numbers 1 to 2001, find how many produced the same result as
(0^2001), how many produced the same result as (1^2001) and so on. Five
to ten minutes work, that is all.

Relevant Pages

  • Re: Any quick way to find a remainder ?
    ... fw_ho@hotmail.com (Andrew) wrote: ... >What is the remainder if the following numver x is divided by 13. ... Rob Johnson ...
    (sci.math)
  • Re: Dividing By Seven
    ... >> be a pattern with the remainders, and 2 was the answer I came up with. ... take the remainder mod 7 ... You can simplify the calculation still further by using balanced modular ... entirely skipped in the way that Mike got wrong. ...
    (rec.puzzles)
  • Re: Regular Expression
    ... Since the remainder of the string starts with "BEGIN", but but your pattern expects spaces or the beginning of the string, that occurance is skipped and the next " BEGIN " is matched. ...
    (microsoft.public.scripting.vbscript)
  • Re: Any quick way to find a remainder ?
    ... so answer is same remainder as 154Śmod 13 ... that is a^n mod p = a^(n mod (p-1)) mod p I think. ... > I have a problem from a friend, i want to know the solution. ... > What is the remainder if the following numver x is divided by 13. ...
    (sci.math)