# ($396396396\dots$ up to $300$ digits) $\bmod{101}$

Evaluate ($$396396396\dots$$ up to $$300$$ digits) $$\bmod{101}$$

I know that a number when repeated $$(p-1)$$ times is completely divisible by $$p$$ where $$p$$ is a prime number.

But I am not able to understand how to apply that here because here we have repetition in groups of $$3.$$

Edit :-

I did not understand this base conversion thing, does this property ("a number with (p-1) digits repeated, when divided by p gives a remainder of 0, where p is a prime number ") hold true in all bases ? How can we divide numbers with different bases ? Why are we not converting 101 as well to higher base ?

• Which is for instance the rest when dividing $396396396396$ by 101? Dec 29, 2022 at 22:45
• Can you find a divisibility test for $101$ similar to the one for $11$? Dec 29, 2022 at 22:46
• You may also observe that $10^3+10^6+10^9+10^{12} \equiv 0 \pmod{101}$ and use that as follows: $$396396396396\ldots396=396[(10^3+10^6+10^9+10^{12})+10^{12}(10^3+10^6+10^9+10^{12})+\dotsb]$$ Dec 29, 2022 at 23:45
• How can I apply the property stated in the description to this question? Dec 30, 2022 at 16:11
• You have a number that is repeated $100$ times. That number is $396$ Mar 27 at 18:34

An answer if you are really stuck but you should try to find it on your own using comments bellow your initial post. We can write \begin{align} n & = \overbrace{396 \cdots 396}^{100 \ \text{times}}\\ & = \sum_{k=0}^{99} 396\cdot 10^{3k}\\ &= 396\cdot \frac{1000^{100} - 1}{1000 - 1}\\[.3em] \Rightarrow\ \ 999 n &= 396(1000^{100}-1)\end{align}\qquad\qquad
$$101$$ is prime and does not divide $$1000$$ so by Fermat's little theorem $$101$$ divides $$1000^{100} -1,$$ so $$101$$ divides $$999n,\,$$ but $$101$$ does not divide $$999$$, so $$101$$ divides $$n$$, by Euclid's Lemma.
• @Fin27 The "base" (radix) language is just a way of specifying that $\,n\,$ is a particular (polynomial) function $P(b)$ of the base $\,b,\,$ i.e. $\, n = P(b) = a(1+b+b^2+\cdots + b^{p-2}) = a(b^{p-1}-1)/(b-1).\,$ The above proof shows that $\,p\nmid b,b\!-\!1\Rightarrow p\mid P(b)\,$ for all integers $\,a,b\,$ and prime $\,p.\,$ Thus we are not restricted to only those values of $\,a\,$ and $\,b\,$ that arise in radix representation, i.e $\,b\ge 2,\ 0\le a < b.\,$ Rather the proof is really about polynomials of form $P(b)$ closely related to Fermat's little theorem. Mar 28 at 23:40
• @Fin27 In particular given $P(b)$ there is no need to even mention "base" or radix rep. It is merely a convenient way to state the form of the polynomial expression $P(b).\,$ Also the value of the repeated digit string $\,a\,$ plays no role in the proof - it suffices to shows that the divisibility holds for the case $\,a=1,\,$ i.e. the integer with $\,p-1\,$ repeated ones in base $\,b\,$ (an integer of repeated $\,a\,$ digits equals $\,a\,$ times an integer of repeated one digits, so remains divisible by $\,p).\ \$ Mar 29 at 0:49