Fall 2015, problem 5

Note that the last 10 digits of an integer $x$ is the value of $x \mod 10^{10}$. We will consider two cases.

Case 1: $p$ is a factor of $10^{10}$

In this case, $p$ must be either 2 or 5, since $10^{10} = \left(2\times 5 \right)^{10} = 2^{10} \times 5^{10}$, which implies that the only prime factors of $10^{10}$ are 2 and 5. In this case, any integer $n$ ending in 1234567890 has its last ten digits distinct, and is an integer multiple of $p$. As there are infinitely many choices for $n$ (we can choose anything as the leading digits before the final ten), there are infinitely many integer multiples of $p$ such that the last ten digits are all distinct in Case 1.

Case 2: $p$ is not a factor of $10^{10}$

In this case, we must have $\gcd \left(p,10^{10} \right )=1$. This means that any congruence of the form $px\equiv b \pmod {10^{10}}$ for a given integer $b$ has a solution $x$ modulo $10^{10}$. In particular, this implies that there exists a positive integer $N_0$ such that $N_0 p \equiv 1 \pmod {10^{10}}$. Similarly, there exists a positive integer $k_0$ such that $k_0 p \equiv a \pmod {10^{10}}$, where $a$ is an integer with distinct final ten digits (e.g. take $a=1234567890$). Then any number of the form $\left ( N_0 p \right )^m \cdot k_0 p$, where $m$ is a positive integer, is congruent to $1^{m} \cdot a = a$ modulo $10^{10}$, i.e. has ten distinct final ten digits. Clearly, numbers of the form $\left ( N_0 p \right )^m \cdot k_0 p$ ($m \in \mathbb{Z}^{+}$) are multiples of $p$, and there are infinitely many numbers of this form, as a new number is produced each time as $m$ varies through the positive integers. This means that in Case 2 also, there are infinitely many multiples of $p$ that are congruent to $a$ modulo $10^{10}$, i.e. where the last ten digits are all distinct.

In both cases, the result holds. As the cases are exhaustive, this completes the proof. $\blacksquare$

P.S. I have written things in TeX-style inline using single dollar signs as described on https://www.math.purdue.edu/pow/markdown_guide . But when I preview my post by clicking the "eye" button, the TeX doesn't render. Is this normal?

Edit: I see that it renders upon posting.

Since $ gcd (p,10^{10}) = 1$ there are natural numbers $ a, b$ such that

$$a p = b \cdot 10^{10} + 1$$

This is the well known $ gcd $ theorem. Now let $ N$ be any number that ends in $...1234567890$. Then $ Nap$ will also end in $...1234567890$. There are, of course, infinitely many such $ N$.

Edit: oh, i forgot the two cases $ p=2$ and $p=5$ in which the above argument doesn't work.

For p=2, when $k \in$ {517283946+$m \times 10^{10}$ | $m \in \mathbb{Z}$}, the last 10 digits of 2k are all distinct.

For p=5, when $k \in$ {204693579+$m \times 10^{10}$ | $m \in \mathbb{Z}$}, the last 10 digits of 5k are all distinct.

For all other cases:

For all $1 \leq k_1 \le k_2 \leq 10^{10}$, since $10^{10}$ cannot divide into $k_2-k_1$ and is coprime with $p$, $k_1p$ and $k_2p$ must be distinct elements in $\mathbb{Z}_{10^{10}}$. Therefore, $p$, $2p$, $3p$, ... , $10^{10}p$ is just a permutation of 1, 2, 3, ..., $10^{10}$. One of $p$, $2p$, $3p$, ... , $10^{10}p$ must be 0123456789, and such $k_i$ that the last ten digit of $k_ip$ are all distinct do exist. Futhermore, all $k \in$ {$k_i+m \times 10^{10} | m \in \mathbb{Z}$}, which is an infinite set, satisfy $kp$ has distinct last ten digits.

The last part can also be done using Bezout's Lemma.

Let $n$ be a ten-digit number whose digits are all distinct.

Also let: $a = n \mod p$ and $b = 10^{10} \mod p$.

Since $p$ is prime, $b$ and $p$ are relatively prime.

Therefore, there exists an integer $m$ such that $bm \equiv 1 \mod p$.

Let

$$x_c = (cp - am) 10^{10} + n$$

$$\equiv [b(cp-am)+a] \mod p$$

$$\equiv (bcp-abm+a) \mod p$$

$$\equiv (-a+a) \mod p$$

$$\equiv 0 \mod p$$

Then for any integer $c$ where $cp-am \ge 0$, we have an integer $k_c = x_c \div p$ that satisfies these conditions.

Since there are an infinite number of values $c$ can hold, there are an infinite number of multiples $k_c$.