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.


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.

  • $\begingroup$ What do you mean by "divide"? And what is $r$? $\endgroup$ – Arthur Nov 1 '12 at 14:33
  • $\begingroup$ check the added part above $\endgroup$ – Ameen Nov 1 '12 at 14:37
  • $\begingroup$ 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. $\endgroup$ – Arthur Nov 1 '12 at 14:45
  • $\begingroup$ Then can you explain how is this proved? That given such r for p. then r divides p-1 $\endgroup$ – Ameen Nov 1 '12 at 15:37

Hint $\ $ Notice that the radix $\rm b$ representation of an integer is a polynomial in the radix $\rm\: n = d_0 + d_1 b +\, \cdots\, + d_k b^k.\:$ If $\rm\:b^r\equiv 1\pmod{p}\:$ then we can use this equation as a rewrite rule to reduce all exponents modulo $\rm\:r,\:$ i.e. $\rm\:b^{\,j\,r+k}\equiv (b^r)^j b^k\equiv b^k\pmod p.\:$ As a result, all exponents will be $\rm < r$, so the radix polynomial becomes a sum of polynomials of degree $\rm < r,\,$ i.e. a sum of digit chunks of length $\rm r,\:$ namely

$$\rm\begin{eqnarray} mod\ p\!:\ \, n\ \ \equiv\,\ \ &&\rm d_0 &\!\!+\ &\cdots &\,+\,&\rm d_{\,r-1}\, b^{r -1}\\ + &&\rm d_r &\!\!+\ &\cdots &\,+\,&\rm d_{2r-1} b^{r-1} \\ + &&\rm d_{2r} &\!\!+\ &\cdots &\,+\,&\rm d_{3r-1} b^{r-1}\\ + && && \cdots \end{eqnarray}$$

E.g. $\rm\, mod\ 37\!:\ 10^3\!\equiv 1\:\Rightarrow\: n = 123456790\equiv 123\cdot 10^6+456\cdot 10^3+790.\:$ Squaring $\rm\:10^3\equiv 1\:$ yields $\rm\:10^6\equiv 1,\:$ hence substituting these yields $\rm\: n\equiv 123\!+\!456\!+\!790\equiv 1369.\:$ Repeating on this we have $\rm\:1369 = 1\cdot 10^3 + 369\equiv 1\!+\!369$ $\equiv 370\equiv 0\pmod{37}$. Hence, as desired, we have split $\rm\:n\:$ into chunks of $\rm\:r = 3$-digit numbers, and summed them to test divisibility by $37$. In fact this method yields the value of $\rm\: n\ mod\ 37.$

  • $\begingroup$ I get what you're saying, but i still don't get it. How to use this to prove that r which is the smallest possible value of digits per partition is a divisor or p-1. If you can clarify more, i'd be thankful. $\endgroup$ – Ameen Nov 1 '12 at 17:28
  • $\begingroup$ @Ameen Since $\rm\:b^{p-1}\!\equiv 1\:$ it follows that the order of $\rm\,b\,$ divides $\rm\:p-1.\:$ See this answer for a proof. $\endgroup$ – Bill Dubuque Nov 1 '12 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.