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
    Then can you explain how is this proved? That given such$r$for p. then$r$divides p-12012-11-01

1 Answers 1

1

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.$

  • 0
    @Ameen Since $\rm\:b^{p-1}\!\equiv 1\:$ it follows that the order of $\rm\,b\,$ divides $\rm\:p-1.\:$ See [this answer](http://math.stackexchange.com/a/127118/242) for a proof.2012-11-01