Competition problem — Number theory

Library / /270 of 520

Number theory Difficulty 6.1 National olympiad Prove it

Property 6 If $(a, m)=1$ , then there exists an integer $b$ , such that $a b \equiv 1(\bmod m)$ . This $b$ is called the number-theoretic inverse of $a$ modulo $m$ , denoted as $a^{-1}(\bmod m)$ , and is often simply written as $a^{-1}$ when there is no risk of confusion.

Solution

By Bézout's Theorem, we know there exist integers $x, y$ such that
$a x + m y = 1.$

Thus, $m \mid a x - 1$ , i.e., $a x \equiv 1 \pmod{m}$ , so there exists a $b$ that satisfies the condition.

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.