# Need help in understanding the method used in solution to find $676767....$(208 digits) mod 53 [duplicate]

Question :- $$676767....$$(208 digits) mod 53

Solution given :- 67 has been assumed to be k in some base higher than 67, so 67 would be a single digit in that base, let it be k

So question turns out to $$kkkk...$$(104 times) mod 53 which will equate to 0 since a number with (p-1) digits repeated, when divided by p gives a remainder of 0 , where p is a prime number

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 53 as well to higher base ?

• Are you familiar with Fermat's little theorem: $a^{p-1}$ gives remainder $1$ when divided by $p$ if $a$ is not divisible by $p$? Mar 27 at 17:53
• Note: you have to be at least a little careful with the base. $4444$ is not divisible by $5$, for example.
– lulu
Mar 27 at 18:11
• This (common) argument is explained in the linked dupe (and many other answers). Mar 27 at 18:46
• I simplified the argument in the linked dupe. Note that the linked dupe is one of your questions a few months prior. Hopfully by now the general method is clear (if not please ask questions in the linked dupe - not here - since this may get deleted since there in nothing new here). Mar 27 at 19:14

Base conversion not needed.

The originally presented number can be re-expressed as

$$67 \times \left[ ~1 + (10^2) + (10^2)^2 + \cdots + (10^2)^{103} ~\right]. \tag1$$

Using the formula for the partial sum of a geometric series, you have that

$$1 + x + x^2 + \cdots + x^n = \frac{x^{n+1} - 1}{x-1}.$$

This means that the expression in (1) above can be re-expressed as

$$67 \times \frac{(10^2)^{104} - 1}{10^2 - 1} = 67 \times \frac{(10^4)^{52} - 1}{10^2 - 1}. \tag2$$

Here is where things get tricky.

$$\pmod{53},~$$ you have that $$(10^2 - 1) \not\equiv 0.$$

As has already been indicated by one of the comments, by Fermat's Little Theorem, you have that $$~(10^4)^{52} - 1 \equiv 0 \pmod{53}.$$

So, in (2) above, the denominator is not $$~\equiv 0 \pmod{53}~$$ and one of the factors in the numerator is $$~\equiv 0 \pmod{53}.$$

So, the overall expression must evaluate to $$~0 \pmod{53}.$$

• Please strive not to post more (dupe) answers to dupes of FAQs, cf. recent site policy announcement here. Mar 27 at 18:18
• @PeterPhipps +1 : nice catch, thanks. answer edited. Mar 27 at 18:24