Proof that adding an integer $k$ to the end of a prime $p$, $p$ times makes the new value divisible by $p$

44 Views Asked by At

This was made as a remark in the last step of the proof to this problem below. In short, suppose we have prime $p$ such that we can express $p$ by its digits as $p=a_n\cdots a_1a_0$ then writing the new number $p'=a_n\cdots a_1a_0kkk\cdots k$, where $k$ is an integer that is written $p$ times, we get that $p|p'$


enter image description here

1

There are 1 best solutions below

10
On BEST ANSWER

This is done by the Pigeonhole Principle. Take the $p$ numbers (call them $b_n$, where $n$ stands for the number of digits) as mentioned and assume none is divisible by $p$, as otherwise we are done.

Now as we have $p-1$ possible remainders and $p$ numbers by the Pigeonhole Principle we must have at least to of them that leave the same remainder upon division by $p$, assume they are $b_m$ and $b_n$ (WLOG $m > n)$. Then we have:

$$p \mid b_m - b_n = b_{m-n}\cdot10^n$$

However as $\gcd(p,10)=1$ we have that $p\mid b_{m-n}$, which is a contradiction. Hence the proof.