A prime number is called an absolute prime if every permutation of its digits in base 10 is also a prime number. For example: 2, 3, 5, 7, 11, 13 (31), 17 (71), 37 (73) 79 (97), 113 (131, 311), 199 (919, 991) and 337 (373, 733) are absolute primes. Prove that no absolute prime contains all of the digits 1, 3, 7 and 9 in base 10.
I am to use a residue system with modulo 7 ... But, I can't understand the residue system. ... Is there another simpler way?
On
The key to this problem is that if you run through all the permutations of $1,3,7,9,$ you find that they cover all the congruence classes modulo $7$. For example, $1379\equiv 0 \pmod7$. Now suppose we are given the digits $1,1,1,3,3,7,9.$ Lay one copy of each digit aside for the momemnt, leaving $1,1,3$. We start with $1130000$, and we find $$ 1130000\equiv 4\pmod7.$$ Now, we only need to find permutation of $1379$ that is congruent to $3$ modulo $7.$ As it happens $$1739\equiv3\pmod7,$$ so we have that $$1131739=1130000+1739\equiv4+3\equiv0\pmod7.$$ That is, $11317139$ is divisible by $7$, so no number formed from the digits $1,1,1,3,3,7,9$ is an absolute prime.
I leave it to you to find the relevant permutations of $1379$ and to convert the foregoing example to a proof.
Observe that if you mod powers of 10 by 7 you get a pattern:
$$ 10^0 = 1 \mod 7$$ $$ 10^1 = 3 \mod 7$$ $$ 10^2 = 2 \mod 7$$ $$ 10^3 = 6 \mod 7$$ $$ 10^4 = 4 \mod 7$$ $$ 10^5 = 5 \mod 7$$ $$ 10^6 = 1 \mod 7$$ $$ 10^7 = 3 \mod 7$$
etc... So it cycles. Any number can be represented as the sum of powers of $10$ and a digit from $0$ to $9$. So for instance:
$$123 = 1 \cdot 10^2 + 2 \cdot 10 + 3 \cdot 10^0$$
We can exploit the additive nature of modular arithmetic to calculate $123 \mod 7$
$$ \begin{align} 123 &= 1 \cdot 10^2 + 2 \cdot 10 + 3 \cdot 10^0 \mod 7 \\ &= 1 \cdot 2 + 2 \cdot 3 + 3 \cdot 1 \mod 7 \\ &= 2 + 6 + 3 \mod 7 \\ &= 8 + 3 \mod 7 \\ &= 11 \mod 7 \\ &= 4 \mod 7 \end{align}$$
So we have a prime number that contains $1$, $3$, $9$, $7$. We can break this number up into parts as done above and exploit additivity to give us $7$ cases.
$$ 0 + 1 \cdot 10^k + 3 \cdot 10^m + 7 \cdot 10^n + 9 \cdot 10^p = \hspace{0.1in} ? \mod 7$$ $$ 1 + 1 \cdot 10^k + 3 \cdot 10^m + 7 \cdot 10^n + 9 \cdot 10^p = \hspace{0.1in} ? \mod 7$$ $$ 2 + 1 \cdot 10^k + 3 \cdot 10^m + 7 \cdot 10^n + 9 \cdot 10^p = \hspace{0.1in} ? \mod 7$$ $$ 3 + 1 \cdot 10^k + 3 \cdot 10^m + 7 \cdot 10^n + 9 \cdot 10^p = \hspace{0.1in} ? \mod 7$$ $$ 4 + 1 \cdot 10^k + 3 \cdot 10^m + 7 \cdot 10^n + 9 \cdot 10^p = \hspace{0.1in} ? \mod 7$$ $$ 5 + 1 \cdot 10^k + 3 \cdot 10^m + 7 \cdot 10^n + 9 \cdot 10^p = \hspace{0.1in} ? \mod 7$$ $$ 6 + 1 \cdot 10^k + 3 \cdot 10^m + 7 \cdot 10^n + 9 \cdot 10^p = \hspace{0.1in} ? \mod 7$$
However, we know that $10^k$, $10^m$, $10^n$, and $10^p \in \{ 1, 3, 2, 6, 4, 5 \}$ mod $7$. One important thing to note is that if no aditional digits besides $9$, $3$, $7$, and $1$ are used, then you can only consider the set $\{ 1, 3, 2, 6 \}$ as there can be no other power of 10 except the first $4$. Furthermore, in the other cases, you may be just using one more digits, meaning you can't necessarily use the number $5$.
In the first case, $9 \cdot 6 + 3 \cdot 2 + 1 \cdot 3 + 7 \cdot 1 = 70$ which is divisible by $7$, hence whatever that number was is also divisible by $7$. And so a permutation exists.
Can you continue with the other permutations?