3
$\begingroup$

Given a number $n$ and a prime number $p$, we aim to divide $n$ into $r$ digit numbers and sum them to check $n$'s divisibility by $p$.

I'm asked to prove that $r$ is a divisor of $p-1$. I think that we need to use fermat's little theorem for this purpose, but I can't get anywhere from there.

Your help is appreciated.

EDIT:

Given $n = 562437487$ and $p=3$, one way to check for divisibility of $n$ by $p$ is to sum all numbers in $n (5 + 6 + 2 + 4 + 3 + 7 + 4 + 8 + 7 = 46)$ and check for the result's divisibility by $p$. Hence, $r$ here is equal to $1$ since we are adding all the digits in n together. For other prime numbers such as $13$, $r$ is $6$ not $1$ and so on.

  • 0
    What do you mean by "divide"? And what is $r$?2012-11-01
  • 0
    check the added part above2012-11-01
  • 0
    Well, this has to do with divisibility of $b^r - 1$ by $p$, where $b$ is your base (usually $10$). It is guaranteed to be a finite $r$ for any $p$ other than divisors of $b$, and you don't need Fermat's for that. Finding the specific number might take some work, though.2012-11-01
  • 0
    Then can you explain how is this proved? That given such r for p. then r divides p-12012-11-01

1 Answers 1