1
$\begingroup$

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 ?

$\endgroup$
8
  • $\begingroup$ Which is for instance the rest when dividing $396396396396$ by 101? $\endgroup$
    – dan_fulea
    Dec 29, 2022 at 22:45
  • 1
    $\begingroup$ Can you find a divisibility test for $101$ similar to the one for $11$? $\endgroup$
    – Ross Millikan
    Dec 29, 2022 at 22:46
  • $\begingroup$ 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]$$ $\endgroup$
    – Anurag A
    Dec 29, 2022 at 23:45
  • $\begingroup$ How can I apply the property stated in the description to this question? $\endgroup$
    – Fin27
    Dec 30, 2022 at 16:11
  • $\begingroup$ You have a number that is repeated $100$ times. That number is $396$ $\endgroup$
    – Ross Millikan
    Mar 27 at 18:34

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thank you! But iam looking for a solution where I could use the property stated in the description of question $\endgroup$
    – Fin27
    Dec 30, 2022 at 16:12
  • $\begingroup$ @Fin27 this property comes from Fermat's little theorem, so this proof is sort of using it. The proof is the similar, no matter the number of digits of the number that is beeing repeted. $\endgroup$
    – Zag
    Dec 30, 2022 at 16:38
  • $\begingroup$ @BillDubuque My doubt :- 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 ? $\endgroup$
    – Fin27
    Mar 28 at 14:09
  • $\begingroup$ @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. $\endgroup$
    – Bill Dubuque
    Mar 28 at 23:40
  • $\begingroup$ @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).\ \ $ $\endgroup$
    – Bill Dubuque
    Mar 29 at 0:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .