Maths Olympiad Prep

Library / /13 of 23

, 2023

Number theory Difficulty 3.1 AMC 10/12 Prove it Canada

A positive integer is divisible by 3 exactly when the sum of its
digits is divisible by 3.

A positive integer is divisible by 4 exactly when the positive integer
formed by its last two digits is divisible by 4. For example:

38163816 is divisible by 33, since 3+8+1+6=183+8+1+6=18 and 1818 is divisible by 33;
38173817 is not divisible by
33, since 3+8+1+7=193+8+1+7=19 and 1919 is not divisible by 33;
38163816 is divisible by 44, since 16 is divisible by 44;
38173817 is not divisible by
44, since 17 is not divisible by
44.

In each part that follows, AA,
BB and CC are non-zero digits (1, 2, 3, 4, 5, 6,
7, 8, or 9), and not necessarily distinct.

The five-digit positive integer 4B5B24\,B\,5B\,2 is divisible by 33. What are the possible values of the
non-zero digit BB?
The five-digit positive integer ABABAABABA is divisible by 44 and not divisible by 3. Determine the
number of different pairs of non-zero digits AA and BB that are possible.
A positive integer, tt, is equal to the product of the
four-digit positive integer ACA2A\,CA\,2
and the three-digit positive integer BACBAC; that is, t=ACA2×BACt=A\,CA\,2\times BAC. If tt is divisible by 15 and not divisible by
12, determine the number of different triples of non-zero digits AA, BB, CC
that are possible.

Solution

The five-digit positive integer 4B5B24B5B2 is divisible by 3 exactly when the
sum of its digits, 4+B+5+B+2=2B+114+B+5+B+2=2B+11
is divisible by 3.

Checking the possible values of BB,

Value of B\boldsymbol{B}
1
2
3
4
5
6
7
8
9

Value of 2B+11\boldsymbol{2B+11}
13
15
17
19
21
23
25
27
29

we get that 2B+112B+11 is divisible
by 3 when B=2B=2, B=5B=5 and B=8B=8.
Solution 1

Since ABABAABABA is not divisible by
3, then A+B+A+B+A=3A+2BA+B+A+B+A=3A+2B is not
divisible by 3.

Since 3A3A is divisible by 3 for all
possible values of the digit AA,
then if 2B2B were also divisible by 3
(that is, if B=3B=3, 6, 9), it would
be the case that 3A+2B3A+2B is divisible
by 3.

Since 3A+2B3A+2B is not divisible by 3,
then 2B2B cannot be divisible by 3
and so the possible values of BB are
1, 2, 4, 5, 7, 8.

Since ABABAABABA is divisible by 4, then
the two-digit positive integer BABA
is divisible by 4.

For each of the possible values of BB, namely B=1B=1, 2, 4, 5, 7, 8, we determine the
values of AA for which BABA is divisible by 4 .

For example when B=1B=1, the two-digit
positive integer 1A1A is divisible by
4 exactly when A=2A=2 or A=6A=6.

In the table below, we determine the remaining pairs AA and BB that are possible.

B\boldsymbol{B}
A\boldsymbol{A}
(A,B)\boldsymbol{(A,B)}

1
2, 6
(2,1)(2,1), (6,1)(6,1)

2
4, 8
(4,2)(4,2), (8,2)(8,2)

4
4, 8
(4,4)(4,4), (8,4)(8,4)

5
2, 6
(2,5)(2,5), (6,5)(6,5)

7
2, 6
(2,7)(2,7), (6,7)(6,7)

8
4, 8
(4,8)(4,8), (8,8)(8,8)

Thus, there are 12 different pairs of non-zero digits AA and BB that are possible.

Solution 2

Since ABABAABABA is divisible by 4,
then it is also divisible by 2 and thus even.

Since ABABAABABA is even, then the ones
digit is even, and so the possible values of AA are 2, 4, 6, 8.

Since ABABAABABA is divisible by 4, then
the two-digit positive integer BABA
is divisible by 4.

For each of the possible values of AA, namely A=2A=2, 4, 6, 8, we determine the values
of BB for which BABA is divisible by 4 .

For example when A=2A=2, the two-digit
positive integer B2B2 is divisible by
4 exactly when $B=1, 3, 5, 7, and\text{and} }
9.$

When A=4A=4, the two-digit positive
integer B4B4 is divisible by 4
exactly when $B=2, 4, 6, and\text{and} }
8.$

When A=6A=6, the two-digit positive
integer B6B6 is divisible by 4
exactly when $B=1, 3, 5, 7, and\text{and} }
9.$

When A=8A=8, the two-digit positive
integer B8B8 is divisible by 4
exactly when $B=2, 4, 6, and\text{and} }
8.$

Finally, we consider the fact that ABABAABABA is not divisible by 3.

As was shown in Solution 1, the possible values of BB are 1, 2, 4, 5, 7, 8 (B3,6,9B\neq 3, 6, 9).

Combining this information with the previous values of AA and BB, we get that the possible pairs of
non-zero digits (A,B)(A, B) are (2,1)(2,1), (2,5)(2,5), (2,7)(2,7), (4,2)(4,2), (4,4)(4,4), (4,8)(4,8), (6,1)(6,1), (6,5)(6,5), (6,7)(6,7), (8,2)(8,2), (8,4)(8,4), and (8,8)(8,8).

Thus, there are 12 different pairs of non-zero digits AA and BB that are possible.
If t=ACA2×BACt=ACA2\times BAC is
divisible by 15, then tt is
divisible by both 5 and 3.

An integer is divisible by 5 exactly when its ones digit is 0 or 5, and
so ACA2ACA2 is not divisible by
5.

Since t=ACA2×BACt=ACA2\times BAC is divisible
by 5 and ACA2ACA2 is not, then BACBAC must be divisible by 5, which means
that C=5C=5 (since CC is a non-zero digit).

Substituting C=5C=5, we get t=A5A2×BA5t=A5A2\times BA5.

Since tt is divisible by 3 and 3
is a prime number, then at least one of A5A2A5A2 or BA5BA5 is divisible by 3, and so A+5+A+2=2A+7A+5+A+2=2A+7 is divisible by 3, or B+A+5B+A+5 is divisible by 3, or both are
divisible by 3.

Since tt is not divisible by 12,
but tt is divisible by 3, then tt is not divisible by 4.

The three-digit integer BA5BA5 is not
divisible by 2 (and thus not divisible by 4) for all possible values of
AA, and so the four-digit integer
A5A2A5A2 must not be divisible by 4
.

The four-digit integer A5A2A5A2 is
divisible by 4 when the two-digit integer A2A2 is divisible by 4, or when A=1A=1, 3, 5, 7, or 9, and so the possible
values of AA are 2, 4, 6, 8.

Finally, we return to the requirement that t=A5A2×BA5t=A5A2\times BA5 is divisible by 3,
meaning that at least one of 2A+72A+7
or B+A+5B+A+5 is divisible by 3.

When A=2A=2, 2A+7=112A+7=11 which is not divisible by 3 and
so B+A+5=B+7B+A+5=B+7 must be divisible by
3. B+7B+7 is divisible by 3 exactly
when B=2,5B=2,5, or 8, and so there are
3 triples AA, BB, CC
that are possible in this case.

When A=4A=4, 2A+7=152A+7=15 which is divisible by 3, which
means that BB can be equal to any
non-zero digit, and so there are 9 triples AA, BB, CC
that are possible in this case.

When A=6A=6, 2A+7=192A+7=19 which is not divisible by 3 and
so B+A+5=B+11B+A+5=B+11 must be divisible by
3. B+11B+11 is divisible by 3 exactly
when B=1B=1, 4, or 7, and so there are
3 triples AA, BB, CC
that are possible in this case.

When A=8A=8, 2A+7=232A+7=23 which is not divisible by 3 and
so B+A+5=B+13B+A+5=B+13 must be divisible by
3. B+13B+13 is divisible by 3 exactly
when B=2B=2, 5 or 8, and so there are
3 triples AA, BB, CC
that are possible in this case.

Therefore, there are 3+9+3+3=183+9+3+3=18
different triples of non-zero digits AA, BB, CC
that are possible.

Want a route through all this instead of an archive? The track puts 2,444 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.