3
$\begingroup$

How we can prove divisible rules for larger primes like $73$?

$n$ is dividable by $73$ if and only if $73|a-b$ where $a$ is number from first $4$ digits $b$ is number from rest of digits

example $$ 43181169 \rightarrow 4318 -1169 = 3149 = 47 \cdot 67 $$

$\endgroup$
  • 1
    $\begingroup$ This rule does not work. $75482$ is divisible by $73$, but $7548-2=7546$ is not. $\endgroup$ – kccu May 13 at 23:45
  • 1
    $\begingroup$ Hint $\ 10^{\large 4}\equiv -1\pmod{73}\ \ \ $ $\endgroup$ – Bill Dubuque May 13 at 23:50
  • 1
    $\begingroup$ Your rule should have $b$ is the last $4$ digits of $n$, and $a$ are all but the last $4$. When $n$ is $8$ digits long these happen to coincide, but as my example shows this doesn't work in general. $\endgroup$ – kccu May 13 at 23:51
3
$\begingroup$

$\begin{align}{\bf Hint}\ \ \bmod 73\!:\,\ \color{#c00}{10^{\large 4}\equiv -1}\ \Rightarrow\ &\ d_0\,+\, d_1 \color{#c00}{10^{\large 4}} + d_2 \color{#c00}{10^{\large 8}}+\ \cdots\ \ \text{(in radix } 10^{\large 4}\ \text{with digits } d_i )\\[.2em] \equiv\ &\ d_0\, -\, d_1\ \ \ +\ \ \ d_2\ \ \ \ \ \ -\ \cdots\ \ \text{(alternating digit sum)}\end{align}$

Same mod $\,137\,$ by $\, 10^{\large 4}+1 = 73\cdot 137.\ $

If we consider an integer in radix $\, 10^{\large 4}$ as a polynomial $\,P(10^{\large 4})$ in the radix then above is

$\!\bmod\, 10^{\large 4}+1\!:\,\ \color{#c00}{10^{\large 4}\equiv -1}\,\Rightarrow\, P(\color{#c00}{10^{\large 4}})\equiv P(\color{#c00}{-1}) \equiv\, $ alternating sum of digits in radix $10^{\large 4} $

which is the radix $10^{\large 4}$ analog of casting $11$'s in radix $10,\,$ i.e. the common test for divsibility by $11$, where the above inference employs the Polynomial Congruence Rule.

Remark $ $ The same method works if we replace $\,73\,$ by any integer $\,n\,$ coprime to $\,10\,$ since then $\,10^{\large k}\equiv 1 \pmod{\!n}$ for some integer $\,k>1,\,$ e.g. we can choose $\, k = \phi(n)\,$ by Euler's Theorem. The least such $\,k\,$ is known as the order of $10$ modulo $\,n,\,$ and it must divide $\,\phi(n).$

See also the closely related topic of periodicity of decimal expansion of rationals (fractions). e.g. $1/73\, =\, 0.\overline{01369863}\,$ repeats with period $\,\color{#0a0}8,\,$ and $\,0136 + 9863 = 9999,\,$ because $\!\bmod 73\!:\,\ \color{#c00}{10^{\large 4}\equiv -1}\,\Rightarrow\, 10^{\large\color{#0a0} 8}\equiv 1\,$ so $\,10\,$ has order $\,\color{#0a0}8\,$ modulo $73,\,$ by the Order Test.

$\endgroup$
1
$\begingroup$

If $a\equiv b\pmod{p}$, then you have $a^k\equiv b^k\pmod{p}$. So, for any polynomial with coeffs. in $\mathbb{Z}$, you can say that $$f(a)\equiv f(b)\pmod{p}$$ here, consider the polynomial $f(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n $. So, $f(10)$ is the number $a_n\cdots a_1a_0$.

As, $10^4\equiv -1\pmod{73}$, we have $f(10^4)=f(-1)$. That means, \begin{align} f(10)& \equiv \overline{a_na_{n-1}\cdots a_1a_0}\\ & \equiv \overline{a_3a_2a_1a_0}+\overline{a_7a_6a_5a_4}\cdot 10^4 + \overline{a_{11}a_{10}a_9a_8}\cdot 10^8+\cdots \\ & \equiv \overline{a_3a_2a_1a_0}-\overline{a_7a_6a_5a_4}+\cdots +(-1)^{\lfloor n/4 \rfloor}\overline{a_na_{n-1}a_{n-2}a_{n-3}}\pmod{73} \end{align} is the remainder when you devide the number by $73$.

In general, if possible, find $k$ such that $10^k\equiv \pm 1\pmod{p}$ and you will have $f(10^k)\equiv f(1)$ or $f(-1)\pmod{p}$, using this property you can check the divisibility. Here you can get some example.

$\endgroup$
  • $\begingroup$ This seems to be essentially the same as what I wrote. Was something there not clear? If so please let me know what that is so that I can improve it. $\endgroup$ – Bill Dubuque May 14 at 0:48
  • $\begingroup$ I have explained it with digits of the number, and tried to show a generalized way as OP stated larger primes like $73$. $\endgroup$ – tarit goswami May 14 at 1:08

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.