Based on 111

Number Theory Level 5

In the decimal number system, we have the remarkable fact that $37\ \text{divides}\ 111\ \ \ \ \text{and}\ \ \ \ 3 + 7 = 10.$ Is there an analogy of this in any other number system? In other words, given a base $b$ , do there exist digits $x, y$ such that $\overline{xy}_b\ \text{divides}\ 111_b\ \ \ \ \text{and}\ \ \ \ x + y = 10_b\ ?$

In your answer, indicate for how many bases $b < 100$ such a pair of digits $x,y$ exists .

Note

A "digit" in base $b$ has values between $0$ and $b-1$ (inclusive). For instance, in base 16 there are 16 digits: $0, 1, 2, 3, 4, 5, 6, 7, 8, 9, \mathrm A\ (=\ 10_{10}), \mathrm B, \mathrm C, \mathrm D, \mathrm E, \mathrm F\ (=\ 15_{10}).$

The answer is 32.

3 solutions

Arjen Vreugdenhil
Sep 30, 2017

From the second equation, $y = b - x$ ; the first equation translates to $a(bx + y) = b^2 + b + 1\ \ \ \ \ \therefore\ \ \ \ \ abx + ab - ax = b^2 + b + 1.$ Considering this equation modulo $b$ , we see that $ax \equiv -1$ , i.e. $ax = mb - 1$ for some integer $m \geq 1$ . Thus $mb^2 + (a - m - 1)b + 1 = b^2 + b + 1\ \ \ \ \ \therefore\ \ \ \ \ mb + (a - m - 1) = b + 1.$ It follows that $m = 1$ and $a - m - 1 = 1$ , so that $a = 3$ . The equation $ax = mb - 1$ translates into $b = 3x + 1.$ This is a necessary and sufficient condition for there to exist a pair of digits with the required property. Naturally, $x = 0$ and $b = 1$ is not meaningful; therefore we count how many integers $x \geq 1$ there are such that $3x + 1 < 100$ ; the answer is $\boxed{32}$ .

Specifically, the first few solutions are $3\cdot 13_4 = 111_4$ $3\cdot 25_7 = 111_7$ $3\cdot 37_{10} = 111_{10}$ $3\cdot 49_{13} = 111_{13}$ $3\cdot 5B_{16} = 111_{16}$

Could you please explain where I went wrong as I don't understand. This is my working (sorry about the layout, I'm not too good with LaTex):

(b^2 + b + 1) / (xb + y) = k (where k is an integer)

x + y = b

Therefore:

[b(b + 1) + 1] / (xb + y) = k

xb + y = Odd (as being even would make k a fraction as the numerator is odd)

Then, testing the possible combination of parities of x,b and y, and seeing if they satisfy the rules:

x, b, y, xb + y = Odd?, x + y = b?

Odd Odd Odd No

Odd Odd Even Yes Yes

Odd Even Odd Yes Yes

Even Odd Odd Yes Yes

Odd Even Even No

Even Odd Even No

Even Even Odd Yes No

Even Even Even No

As x and y are digits, they are at most 9 and at least 1, so b is at most 18 and at least 2. With these possible values of b, I worked out b^2 + b + 1. If this value was prime, then xb + y would have to equal b^2 + b + 1, which is impossible as x and y are less than b (since they are digits used in a base-b value). Therefore, I calculated the other factors of non-primes. Finally, I used these to find the multiples of b that were within 9 under these other factors, and calculated the values of x and y. The values given in my table are only inputted if they fit x + y = b.

b, b^2 + b + 1, Prime?, Other Factors, x,y given (xb + y) and (x + y = b)

2 7 Yes

3 13 Yes

4 21 No 3,7 1,3

5 31 Yes

6 43 Yes

7 57 No 3,19 2,5

8 73 Yes

9 91 No 7,13

10 111 No 3,37 3,7

11 133 No 7,19

12 157 Yes

13 183 No 3,61 4,9

14 211 Yes

15 241 Yes

16 273 No 3,7,13,21,39,91 5,11

17 307 Yes

18 343 No 7,49

Therefore, I got $\boxed{5}$ as my answer?

Stephen Mellor - 3 years, 8 months ago

If $b > 10$ , a "digit" can have a greater value than 9. For instance, in base 16, the "digits" are $0, 1, 2, \dots, 9, \mathrm A, \mathrm B, \dots, \mathrm F$ .

I will clarify this in the problem statement. Apologies for the confusion.

Arjen Vreugdenhil - 3 years, 8 months ago

Scrub Lord
Oct 6, 2017

We have

x + y = b,

bx + y divides b^2 + b + 1, which means bx + b - x divides b^2 + b +1.

Since bx + b - x divides b^2 + b + 1, it also divides (b - 1)(bx + b - x) - x(b^2 +b +1) = b^2 - 3bx - b.

gcd (bx + b - x, b) = 1, therefore bx + b - y divides (b - 3x - 1).

It can be easily shown that |b - 3x - 1| < bx + b - y, which means that b - 3x - 1 = 0. So we have:

b = 3x + 1, y = 2x + 1, and 3bx + 3y = b^2 + b + 1.

Jonathan Quarrie
Oct 2, 2017

I must admit that I can't fully follow Arjen's solution, so I'm just going to put my approach and results down, which is most likely not to be as succinct or as complete (and hopefully stays towards the bottom of the page, to spare much scrolling).

I looked at which integers 111 was divisible by in base 10.

Only two:
- $3$
- $37$

Holding onto the value $3$ as a likely candidate for the lowest common denominator for each $b$ that satisfies this problem, I then established the decimal value ( $dV$ ) necessary to create 111 in every $b$ < 100.

Then, to test the theory, I checked all possible combinations of $b$ digits that added up to $10_{b}$ for each $b < 36$ (except those that had a prime $dV$ ).

With the results confirming a divisor of $3$ , I then counted how many $dV\pmod{3}$ returned a remainder of $0$ for the total count up to $b_{99}$ .

b	Decimal value (dV) for 111 in b	$dV\pmod{3}$	Count of 0s
b2	dV7	$\color{#D61F06}1$	-
b3	dV13	$\color{#D61F06}1$	-
b4	dV21	$\color{#20A900}0$	1
b5	dV31	$\color{#D61F06}1$	-
b6	dV43	$\color{#D61F06}1$	-
b7	dV57	$\color{#20A900}0$	2
b8	dV73	$\color{#D61F06}1$	-
b9	dV91	$\color{#D61F06}1$	-
b10	dV111	$\color{#20A900}0$	3
b11	dV133	$\color{#D61F06}1$	-
b12	dV157	$\color{#D61F06}1$	-
b13	dV183	$\color{#20A900}0$	4
b14	dV211	$\color{#D61F06}1$	-
b15	dV241	$\color{#D61F06}1$	-
b16	dV273	$\color{#20A900}0$	5
b17	dV307	$\color{#D61F06}1$	-
b18	dV343	$\color{#D61F06}1$	-
b19	dV381	$\color{#20A900}0$	6
b20	dV421	$\color{#D61F06}1$	-
b21	dV463	$\color{#D61F06}1$	-
b22	dV507	$\color{#20A900}0$	7
b23	dV553	$\color{#D61F06}1$	-
b24	dV601	$\color{#D61F06}1$	-
b25	dV651	$\color{#20A900}0$	8
b26	dV703	$\color{#D61F06}1$	-
b27	dV757	$\color{#D61F06}1$	-
b28	dV813	$\color{#20A900}0$	9
b29	dV871	$\color{#D61F06}1$	-
b30	dV931	$\color{#D61F06}1$	-
b31	dV993	$\color{#20A900}0$	10
b32	dV1057	$\color{#D61F06}1$	-
b33	dV1123	$\color{#D61F06}1$	-
b34	dV1191	$\color{#20A900}0$	11
b35	dV1261	$\color{#D61F06}1$	-
b36	dV1333	$\color{#D61F06}1$	-
b37	dV1407	$\color{#20A900}0$	12
b38	dV1483	$\color{#D61F06}1$	-
b39	dV1561	$\color{#D61F06}1$	-
b40	dV1641	$\color{#20A900}0$	13
b41	dV1723	$\color{#D61F06}1$	-
b42	dV1807	$\color{#D61F06}1$	-
b43	dV1893	$\color{#20A900}0$	14
b44	dV1981	$\color{#D61F06}1$	-
b45	dV2071	$\color{#D61F06}1$	-
b46	dV2163	$\color{#20A900}0$	15
b47	dV2257	$\color{#D61F06}1$	-
b48	dV2353	$\color{#D61F06}1$	-
b49	dV2451	$\color{#20A900}0$	16
b50	dV2551	$\color{#D61F06}1$	-
b51	dV2653	$\color{#D61F06}1$	-
b52	dV2757	$\color{#20A900}0$	17
b53	dV2863	$\color{#D61F06}1$	-
b54	dV2971	$\color{#D61F06}1$	-
b55	dV3081	$\color{#20A900}0$	18
b56	dV3193	$\color{#D61F06}1$	-
b57	dV3307	$\color{#D61F06}1$	-
b58	dV3423	$\color{#20A900}0$	19
b59	dV3541	$\color{#D61F06}1$	-
b60	dV3661	$\color{#D61F06}1$	-
b61	dV3783	$\color{#20A900}0$	20
b62	dV3907	$\color{#D61F06}1$	-
b63	dV4033	$\color{#D61F06}1$	-
b64	dV4161	$\color{#20A900}0$	21
b65	dV4291	$\color{#D61F06}1$	-
b66	dV4423	$\color{#D61F06}1$	-
b67	dV4557	$\color{#20A900}0$	22
b68	dV4693	$\color{#D61F06}1$	-
b69	dV4831	$\color{#D61F06}1$	-
b70	dV4971	$\color{#20A900}0$	23
b71	dV5113	$\color{#D61F06}1$	-
b72	dV5257	$\color{#D61F06}1$	-
b73	dV5403	$\color{#20A900}0$	24
b74	dV5551	$\color{#D61F06}1$	-
b75	dV5701	$\color{#D61F06}1$	-
b76	dV5853	$\color{#20A900}0$	25
b77	dV6007	$\color{#D61F06}1$	-
b78	dV6163	$\color{#D61F06}1$	-
b79	dV6321	$\color{#20A900}0$	26
b80	dV6481	$\color{#D61F06}1$	-
b81	dV6643	$\color{#D61F06}1$	-
b82	dV6807	$\color{#20A900}0$	27
b83	dV6973	$\color{#D61F06}1$	-
b84	dV7141	$\color{#D61F06}1$	-
b85	dV7311	$\color{#20A900}0$	28
b86	dV7483	$\color{#D61F06}1$	-
b87	dV7657	$\color{#D61F06}1$	-
b88	dV7833	$\color{#20A900}0$	29
b89	dV8011	$\color{#D61F06}1$	-
b90	dV8191	$\color{#D61F06}1$	-
b91	dV8373	$\color{#20A900}0$	30
b92	dV8557	$\color{#D61F06}1$	-
b93	dV8743	$\color{#D61F06}1$	-
b94	dV8931	$\color{#20A900}0$	31
b95	dV9121	$\color{#D61F06}1$	-
b96	dV9313	$\color{#D61F06}1$	-
b97	dV9507	$\color{#20A900}0$	$\boxed{32}$
b98	dV9703	$\color{#D61F06}1$	-
b99	dV9901	$\color{#D61F06}1$	-

Note, however, that the problem did not specify that one of the divisors should be 3. For instance, modulo 9 you have $111_9 = 91_{10}$ , which equals $7 \times 13$ . Thus $14_9$ is a divisor of $111_9$ , and the only reason that it is not a valid solution is that $1 + 4 = 5 \not= 10_9$ .

Now it happens to be true that for all solutions the divisor equals 3 (see my proof), but you cannot assume that this is the case!

Arjen Vreugdenhil - 3 years, 8 months ago

I suppose my solution doesn't actually detail all the steps I took in my (somewhat scientific, rather than mathematical) approach.

The divisors for 111 in base 10 are pretty big clue. The number 3 was my hypothesis, and after testing the theory by dividing $111_{b}$ by all possible combinations of $b$ digits that summed to $10_{b}$ for all $b < 36$ , I had enough data to draw a conclusion that 3 was the important number - which, as you say, happens to be true.

My initial theory was $dV$ values that weren't prime numbers, but, coincidentally, $111_{9}$ proved that incorrect.

Jonathan Quarrie - 3 years, 8 months ago

Here is a nice way to see the pattern in $dV\ \mod\ 3$ : let $b = 3n + a$ , with $a = -1, 0, +1$ . Then $dV = b^2 + b + 1 = (3n + a)^2 + (3n + a) + 1 \\ \equiv a^2 + a + 1\ \mod\ 3.$ Now try the three possible values for $a$ : $\begin{cases} dV \equiv (-1)^2 + 1 + (-1) = 1\ \mod\ 3 & a = -1 \\ dV \equiv 0^2 + 0 + 1 = 1\ \mod\ 3 & a = 0 \\ dV \equiv 1^2 + 1 + 1 = 3 \equiv 0 \ \mod\ 3 & a = +1\end{cases}$ So you see that your pattern of $0, 1, 1, 0, 1, 1, \dots$ continues forever...

Arjen Vreugdenhil - 3 years, 8 months ago

Based on 111

The answer is 32.

3 solutions

0 pending reports