0

A prime number greater than 5, say P, is a factor of N, where N is 1 repeated (P - 1) times.

For e.g.:

  1. 13 is a factor of 111111111111(1 repeated 12 times, don't know a better notation)
  2. 23 is a factor of (22 times 1)

This holds for larger numbers as well.

To check it, I used python as below:

P = 13 (any prime number)

N = '1'*(P-1)

R = N % P

Whenever P is prime(and greater than 5), R = 0. Why does this hold?

2 Answers2

6

Fermat's Little Theorem provides the answer!

It states that for any prime $p$

$$a^{p-1}-1 \text{ mod(p)}\equiv 0$$

If a and p are relatively prime

Plugging in $a=10$ gives us

$$10^{p-1}-1 \text{ mod(p)} \equiv 0$$

Doing some algebra, we get

$$10^{p-1}-1 \text{ mod(p)} \equiv (10-1) * (\sum^{p-2}_{j=0}{10^j})\text{ mod(p)}\equiv0$$

And note that $$ \sum^{p-2}_{j=0}{10^j}\text{ mod(p)}\equiv0$$ is just the sum of a bunch of 1 digits, a repunit as @prets would call it.

Also, note that this is not true when $p=5$, since 10 and 5 are not relatively prime, but it is true for all prime examples greater than 5.

mode_er
  • 677
0

This is incorrect in general , take $5$ as a counter example . Notice that :

$1111= 101*11$