mod 16

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

mod 16

G H J

Reveal topic tags

number theory solved

L

G H BBookmark kLocked kLocked NReply

Source: JBMO 1998

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

165 posts

#1 h Jun 22, 2004, 8:05 AM • 5 Y

Y by Adventure10, Mango247, and 3 other users

Do there exist 16 three digit numbers, using only three different digits in all, so that the all numbers give different residues when divided by 16?

Bulgaria

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Valentin Vornicu

7301 posts

Valentin Vornicu

#2 h Jun 22, 2004, 8:23 AM • 5 Y

Y by Adventure10, Mango247, and 3 other users

The answer is no.

Suppose the answer would be affirmative. Obviuously the three digits cannot be all of the same parity, because we would not be able to cover all the residues modulo 2

Thus there exists at least one even and one odd digit. Suppose WLOG that we have one odd digit and two even digits (the other case can be treated in the same way, replacing the word even with the word odd everywhere). Thus the 8 odd residues modulo 16 must be covered by odd numbers, that is the last digit is the odd one. But there are 9 ways to choose the first two digits, and out of those at least 4 must give odd residue when divided by 8, because the number $\overline{xy}\cdot 10$ ( $\overline{xyz}=\overline{xy}\cdot 10 +z\ \Rightarrow\ \overline{xy}\cdot 10$ ) must pass through all the even residues modulo 16.

The last 4 numbers which give odd residue when divided by 8 must be formed having the last digit y, and odd number, but there are only 3 such numbers, which leads to a contradiction.

Thus the problem is solved.

I am not sure, but I belive this was my solution in the contest.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

72 posts

#3 h Apr 12, 2014, 4:20 AM • 2 Y

Y by Adventure10, Mango247

why there are at least 4 odd residues modulo 8 and why xy.10 must pass through all even residues modulo 16?
(any help is appreciated)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

187 posts

lckihi

#4 h Jan 16, 2019, 4:54 AM • 1 Y

Y by Adventure10

guesswho1729 wrote:

why xy.10 must pass through all even residues modulo 16?

According to the solution above, when there is exactly one odd digit, and the last digit is odd, 8 odd numbers $\overline{xyz}=\overline{xy}\cdot 10 +z$ gives the distinct odd residues 1, 3, 5, 7, 9, 11, 13, 15. So $\overline{xy}\cdot 10$ gives the distinct even residues 0, 2, 4, 6, 8, 10, 12, 14.

guesswho1729 wrote:

why there are at least 4 odd residues modulo 8

From the 8 cases of distinct even residues mentioned above,
$\overline{xy}\cdot 10=16a+0\Rightarrow \overline{xy}\cdot 5=8a+0\Rightarrow \overline{xy}$ is even.
$\overline{xy}\cdot 10=16a+2\Rightarrow \overline{xy}\cdot 5=8a+1\Rightarrow \overline{xy}$ is odd.
$\overline{xy}\cdot 10=16a+4\Rightarrow \overline{xy}\cdot 5=8a+2\Rightarrow \overline{xy}$ is even.
$\overline{xy}\cdot 10=16a+6\Rightarrow \overline{xy}\cdot 5=8a+3\Rightarrow \overline{xy}$ is odd.
$\overline{xy}\cdot 10=16a+8\Rightarrow \overline{xy}\cdot 5=8a+4\Rightarrow \overline{xy}$ is even.
$\overline{xy}\cdot 10=16a+10\Rightarrow \overline{xy}\cdot 5=8a+5\Rightarrow \overline{xy}$ is odd.
$\overline{xy}\cdot 10=16a+12\Rightarrow \overline{xy}\cdot 5=8a+6\Rightarrow \overline{xy}$ is even.
$\overline{xy}\cdot 10=16a+14\Rightarrow \overline{xy}\cdot 5=8a+7\Rightarrow \overline{xy}$ is odd.

So there are exactly 4 odd numbers for $\overline{xy}$ . That happens when $y$ is an odd digit. But there are only 3 choices for $x$ , which leads to a contradiction.

This post has been edited 1 time. Last edited by lckihi, Jan 16, 2019, 5:00 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

237 posts

#5 h Apr 9, 2025, 8:11 PM

Y by

The answer is no
Assume for the sake of contradiction that this is true
Then all $16$ residues exist
and since there are only $16$ total residues in the residue class
there are $8$ odd and $8$ even
Since there are $8$ odd residues
the last digits of these numbers are also odd
and therefore they are odd numbers
$\textbf{Case 1:}$ There is $1$ odd number among the $3$ numbers
Therefore there are only $2$ odd numbers
$\rightarrow \leftarrow$
$\textbf{Case 2:}$ There are $2$ odd numbers among the $3$ numbers
Therefore there are only $8$ total odd numbers among all the numbers formed but that means there are only 2 even numbers
$\rightarrow \leftarrow$
$\textbf{Case 3:}$ All $3$ are odd
Therefore there are $8$ odd numbers
which also means the $16$ numbers that need to be formed are all odd
since all $3$ numbers are odd
$\rightarrow \leftarrow$
$\therefore$ our assumption is false
$\mathbb{Q.E.D}$ $\blacksquare$
:police:

:police:

:juggle:

This post has been edited 1 time. Last edited by Levieee, Apr 9, 2025, 8:24 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a