# Divisible rule for $73$ - how to prove?

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

• This rule does not work. $75482$ is divisible by $73$, but $7548-2=7546$ is not. – kccu May 13 at 23:45
• Hint $\ 10^{\large 4}\equiv -1\pmod{73}\ \ \$ – Bill Dubuque May 13 at 23:50
• 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. – kccu May 13 at 23:51

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

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.

• 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. – Bill Dubuque May 14 at 0:48
• I have explained it with digits of the number, and tried to show a generalized way as OP stated larger primes like $73$. – tarit goswami May 14 at 1:08