Question

1.38. To see if a number, say $\mathbf{562437487}$, is divisible by $\mathbf{3}$, you just add up the digits of its decimalrepresentation, and see if the result is divisible by role="math" localid="1658402816137" $\mathbf{3}$.

( $\mathbf{5}\mathbf{+}\mathbf{6}\mathbf{+}\mathbf{2}\mathbf{+}\mathbf{4}\mathbf{+}\mathbf{3}\mathbf{+}\mathbf{7}\mathbf{+}\mathbf{4}\mathbf{+}\mathbf{8}\mathbf{+}\mathbf{7}\mathbf{=}\mathbf{46}$, so it is not divisible by $\mathbf{3}$).

To see if the same number is divisible by $\mathbf{11}$, you can do this: subdivide the number into pairs ofdigits, from the right-hand end$\mathbf{(}\mathbf{87}\mathbf{,}\mathbf{74}\mathbf{,}\mathbf{43}\mathbf{,}\mathbf{62}\mathbf{,}\mathbf{5}\mathbf{)}$ , add these numbers and see if the sum is divisible by$\mathbf{11}$ (if it's too big, repeat).

How about $\mathbf{37}$? To see if the number is divisible by $\mathbf{37}$, subdivide it into triples from the end$\mathbf{(}\mathbf{487}\mathbf{,}\mathbf{437}\mathbf{,}\mathbf{562}\mathbf{)}$ add these up, and see if the sum is divisible by$\mathbf{37}$ .

This is true for any prime $\mathit{p}$other than$\mathbf{2}$ and $\mathbf{5}$. That is, for any prime $\mathbf{\text{p≠2,5}}$, there is an integer $\mathbf{\text{r}}$such that in order to see if$\mathbf{\text{p}}$ divides a decimal number $\mathbf{\text{n}}$, we break$\mathbf{\text{n}}$ into $\mathbf{\text{r}}$-tuples of decimal digits (starting from the right-hand end), add up these $\mathbf{\text{r}}$-tuples, and check if the sum is divisible by $\mathbf{\text{p}}$.

(a) What is the smallest $\mathbf{\text{r}}$such for $\mathbf{\text{p=13}}$? For$\mathbf{\text{p=13}}$ ?

(b) Show that$\mathbf{\text{r}}$ is a divisor of $\mathbf{\text{p-1}}$.

Short answer

1. The smallest “$r$” for$p=13$ and for$p=17$ are$12,16$ .
2. "$r$" is a divisor of "$p-1$" is depicted.

Step-by-step solution

Step 1: Introduction to the Concept

A tuple is an ordered list (sequence) of elements with a finite number of elements. A sequence (or ordered list) of n elements is called an n-tuple, where n is a non-negative integer. Only one 0-tuple exists, which is referred to as the empty tuple.

Step 2: Solution Explanation

a)

Consider the following example where a decimal number "$\mathrm{N}$" is required to divide up into "$\mathrm{r}$" tuples:

Integer value is,${\mathrm{N}}_{\mathrm{k}}{\mathrm{N}}_{\mathrm{k}-1}\mathrm{...}{\mathrm{N}}_1$

• The above value is the same as multiplying each term by "$10$" to the power of "$r$" and then summing the results.

Then$\mathrm{N}={\mathrm{N}}_1+{\mathrm{N}}_2\times {10}^{\mathrm{r}}+\mathrm{...}+{\mathrm{N}}_{\mathrm{k}}\times {\left({10}^{\mathrm{r}}\right)}^{\mathrm{k}-1}$

• While taking$\mathrm{N}\mathrm{mod}\mathrm{p}$

$\begin{array}{c}\mathrm{Nmodp}=({\mathrm{N}}_1+{\mathrm{N}}_2\times {10}^{\mathrm{r}}+\mathrm{...}+{\mathrm{N}}_{\mathrm{k}}\times {\left({10}^{\mathrm{r}}\right)}^{\mathrm{k}-1})\mathrm{modp}\\ ={\mathrm{N}}_1+{\mathrm{N}}_2+\mathrm{...}+{\mathrm{N}}_{\mathrm{k}}\end{array}$

Observation:${10}^{\mathrm{r}}=1\mathrm{mod}\mathrm{p}-----\left(1\right)$

• By on "Fermat's Little Theorem"

${10}^{\mathrm{p}-1}=1\mathrm{mod}\mathrm{p}-----\left(2\right)$

When comparing equations (1) and (2), the value of "$\mathbf{r}$" is comparable to "$\mathrm{p}-1$",

For $\mathrm{p}=13$, the smallest "$\mathrm{r}$" is:

$\begin{array}{c}\mathrm{r}=\mathrm{p}-1\\ =13-1\\ =12\end{array}$

For $\mathrm{p}=17$, the smallest "$\mathrm{r}$" is:

$\begin{array}{c}\mathrm{r}=\mathrm{p}-1\\ =17-1\\ =16\end{array}$

Hence, the smallest “$\mathbf{r}$” for $\mathrm{p}$=$13$ is $12$and for $\mathrm{p}$=$17$ is$16$ .

Step 3: Solution Explanation

b)

Take the integer "$562437487$" and the value of "$\mathrm{p}$" to be "$37$".

• If the value of "$\mathrm{p}$" is "$37$" divide the integer value into triples from right to left, according to the stated statement.
• As a result,$562437487=\{487,437,562\}$; consequently, the "$\mathbf{r}$" value is "$3$" in this case.
• "$\mathbf{r}$" denotes the number of tuples for which the decimal digits have been broken.

$\begin{array}{c}\mathrm{p}-1=37-1\\ =36\end{array}$

• Then "role="math" localid="1658403981019" $36\mathrm{mod}3=0$" indicating that "$3$" is the divisor of "$36$".

As a result, it can be seen that "r" is a divisor of "$\mathrm{p}-1$".