Competition problem — Number theory

Library / /230 of 520

Number theory Difficulty 5.5 AIME, harder Find the answer

【Question 13】If the product of two natural numbers, when divided by 9, leaves a remainder of 1, we say that these two natural numbers are “mod 9 reciprocals.” For example, $2 \times 5=10$ , when divided by 9 leaves a remainder of 1, so 2 and 5 are “mod 9 reciprocals”; $1 \times 1=1$ , so the “mod 9 reciprocal” of 1 is itself. Clearly, if a natural number has a “mod 9 reciprocal,” then its reciprocal is not unique; for example, 10 is another “mod 9 reciprocal” of 1. Determine whether 1, 2, $3,4,5,6,7,8$ have “mod 9 reciprocals,” and write down the numbers that have “mod 9 reciprocals” and their corresponding smallest “mod 9 reciprocals” respectively. $\qquad$

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Solution

When $a$ and $b$ satisfy $a \times b = 9n + 1$ , $a$ and $b$ are "mod 9 inverses" ( $a$ , $b$ , $n$ are all natural numbers). When $a = 1$ , the smallest "mod 9 inverse" is 1.
When $a = 2$ , the smallest "mod 9 inverse" is 5.
When $a = 3$ , $a \times b = 3b$ , and $3b$ modulo 9 can only be 0, 3, or 6, so 3 has no "mod 9 inverse".
When $a = 4$ , the smallest "mod 9 inverse" is 7.
When $a = 5$ , the smallest "mod 9 inverse" is 2.
When $a = 6$ , $a \times b = 6b$ , and $6b$ modulo 9 can only be 0, 3, or 6, so 6 has no "mod 9 inverse".
When $a = 7$ , the smallest "mod 9 inverse" is 4.
When $a = 8$ , the smallest "mod 9 inverse" is 8.

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

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.