In the table below, the first column contains the four integers given in the problem, the middle column says whether that integer is a multiple of \(7\), and the third column contains the value of \(2A+3B+C\).
| \(\boldsymbol{ABC}\) | Multiple of 7? | \(\boldsymbol{2A+3B+C}\) |
|---|---|---|
| \(392\) | yes (\(7\times56\)) | \(35\) |
| \(487\) | no | \(39\) |
| \(638\) | no | \(29\) |
| \(791\) | yes (\(7\times113\)) | \(42\) |
The two integers that are multiples of \(7\) have the property that \(2A+3B+C\) is also a multiple of \(7\), and the two integers that are not multiples of \(7\) have the property that \(2A+3B+C\) is not a multiple of \(7\).
The integer \(ABC\) is equal to \(100A+10B+C\). Observe that \(100=7\times 14+2\) and \(10=7+3\), so we have that \[\begin{align*} ABC &= 100A+10B+C \\ &= [7(14)+2]A+(7+3)B+C \\ &= 7(14A+B)+(2A+3B+C)\end{align*}\] which can then be rearranged to get \(ABC-7(14A+B)=2A+3B+C\).
We are assuming that \(ABC\) is a multiple of \(7\), so the expression \(2A+3B+C\) is equal to the difference of two multiples of \(7\), and so it must be a multiple of \(7\).
Using the calculation from part (b), \(ABC=7(14A+B)+2A+3B+C\) for any three-digit positive integer \(ABC\). If \(2A+3B+C\) is a multiple of \(7\), then \(ABC\) is the sum of two multiples of \(7\) and so must be a multiple of \(7\).
The combined result of parts (b) and (c) is that a three-digit integer \(ABC\) is a multiple of \(7\) if and only if the integer \(2A+3B+C\) is a multiple of \(7\). To answer the question in this part, we will first establish a similar fact about six-digit integers.
To do this, we first divide each of \(10\), \(10^2\), \(10^3\), \(10^4\), and \(10^5\) by \(7\) to find the quotient and remainder. \[\begin{align*} 10 &= 7+3 \\ 10^2 &= 7(14)+2 \\ 10^3 &= 7(142)+6 \\ 10^4 &= 7(1428)+4 \\ 10^5 &= 7(14285)+5\end{align*}\]
Since \(ABCDEF = A\times 10^5+B\times10^4+C\times10^3+D\times10^2+E\times10+F\), we can substitute the equations above and rearrange to get that \[ABCDEF = 7(14285A+1428B+142C+14D+E)+(5A+4B+6C+2D+3E+F)\] and since \(7(14285A+1428B+142C+14D+E)\) is a multiple of \(7\), a similar argument to those used in parts (b) and (c) imply that the integer \(ABCDEF\) is a multiple of \(7\) if and only if the quantity \(5A+4B+6C+2D+3E+F\) is a multiple of \(7\).
We will now prove that \(ABCDEF\) is a multiple of \(7\) if and only if \(BCDEFA\) is a multiple of \(7\). First, assume that \(ABCDEF\) is a multiple of \(7\). By the fact established above, the integer \(5A+4B+6C+2D+3E+F\) is a multiple of \(7\). Though it may seem like a strange observation, this implies that \(3(5A+4B+6C+2D+3E+F)\) must be a multiple of \(7\). Expanding and grouping some terms, we have \[\begin{align*} 3(5A+4B+6C+2D+3E+F) &= 15A+12B+18C+6D+9E+3F \\ &= (14A+7B+14C+7E) \\ & \hspace{5mm}+(A+5B+4C+6D+2E+3F) \\ &= 7(2A+B+2C+E) \\ & \hspace{5mm}+ (5B+4C+6D+2E+3F+A)\end{align*}\] and so \(7(2A+B+2C+E) + (5B+4C+6D+2E+3F+A)\) is a multiple of \(7\). This implies that \(5B+4C+6D+2E+3F+A\) is a multiple of \(7\), and by the fact established above, the six-digit integer \(BCDEFA\) is a multiple of \(7\).
We now suppose that \(BCDEFA\) is a multiple of \(7\). We have already shown above that if the digits are "cycled" to the left, then the integer obtained is also a multiple of \(7\). Applying this several times, we have that \(CDEFAB\) is a multiple of \(7\), as are \(DEFABC\), \(EFABCD\), \(FABCDE\), and finally \(ABCDEF\).
As an example, you can verify for yourself that \(314517\) is a multiple of \(7\), and so are each of \(145173\), \(451731\), \(517314\), \(173145\), and \(731451\). Similarly, the integer \(215739\) is not a multiple of \(7\), and neither are any of \(157392\), \(573921\), \(739215\), \(392157\), and \(921573\).
Note: The assumption that none of the digits of \(ABCDEF\) are zero implies that each of the integers obtained by cycling the digits is a six-digit integer. If we were to allow digits equal to \(0\), the claim remains true, but in practice we may need to include "leading zeros". For example, cycling the digits of the integer \(300412\) in this way would lead to \(004123\) (which is really a four-digit integer), then \(041230\), \(412300\), \(123004\), and so on.
While we will not include proofs here, we will list a few ways that the result in (d) can be generalized.
If the number of digits in an integer is any positive multiple of \(6\), then the result of part (d) still holds. That is, if \(n\) has \(6k\) digits for some \(k\geq 1\), then \(n\) is a multiple of \(7\) if and only if the integer obtained by cycling its digits is a multiple of \(7\).
For any prime number \(p\), other than \(2\) and \(5\), if an integer has \(p-1\) digits, then it is a multiple of \(p\) if and only if the integer obtained by cycling its digits is a multiple of \(p\). For example, a \(16\)-digit integer is a multiple of \(17\) if and only if the integer obtained by cycling its digits is a multiple of \(17\). The reason this fails for \(p=2\) and \(p=5\) is related to the fact that \(2\) and \(5\) are the prime factors of \(10\), which is the base of our number system.
Suppose \(k\) is an integer. The Euler Totient Function of \(k\), denoted by \(\varphi(k)\), is defined to be the number of integers \(m\) with \(1\leq m\leq k\) such that \(\gcd(m,k)=1\). For example, \(\varphi(6)=2\) since \(1\) and \(5\) are the only integers between \(1\) and \(6\) inclusive that have a \(\gcd\) of \(1\) with \(6\). \(\varphi(21)=12\) since there are exactly \(12\) integers \(m\) from \(1\) to \(21\) inclusive with the property that \(\gcd(m,21)=1\). They are \(1,2,4,5,8,10,11,13,16,17,19,20\).
If \(k\) is an integer that is neither a multiple of \(2\) nor a multiple of \(5\), then any \(\varphi(k)\)-digit integer is a multiple of \(k\) if and only if the integer obtained by rotating its digits is a multiple of \(k\). For example, the \(12\)-digit integer \(439874621235\) is a multiple of \(21\), and so are \(398746212354\), \(987462123543\), and so on.
One of the key observations for proving something like this is a result due to Euler that says that when \(a\) and \(k\) are nonzero integers with \(\gcd(a,k)=1\), the remainder when dividing \(a^{\varphi(k)}\) by \(k\) is \(1\).