0
$\begingroup$

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 ?

$\endgroup$
4
  • $\begingroup$ 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$? $\endgroup$
    – J. W. Tanner
    Mar 27 at 17:53
  • 1
    $\begingroup$ Note: you have to be at least a little careful with the base. $4444$ is not divisible by $5$, for example. $\endgroup$
    – lulu
    Mar 27 at 18:11
  • $\begingroup$ This (common) argument is explained in the linked dupe (and many other answers). $\endgroup$
    – Bill Dubuque
    Mar 27 at 18:46
  • $\begingroup$ 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). $\endgroup$
    – Bill Dubuque
    Mar 27 at 19:14

1 Answer 1

Reset to default
2
$\begingroup$

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

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

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