Interpretation of $ax\equiv 1 \bmod n$

73 Views Asked by At

$ax\equiv 1 \bmod n$ is stated to have a solution if and only if $(a,n)=1$.
Based on this have a few questions:
(i) This means, $\exists b \in \mathbb {Z}, ax-1= bn \implies (ax-bn)=1$.
(ii) Can the last equality be viewed as a variant of the usual equality : $ax + by =1$. If so, what is the logic.
In terms of the geometrical interpretation , it is having an opposite slope for the straight line.

(iii) How can I interpret the equality $a\equiv 1 \bmod n$, if valid. I mean the difference from the title equality, if valid, by removal of variable $x$.

1

There are 1 best solutions below

8
On BEST ANSWER

(i)$$ax \equiv 1 \pmod{n}$$ does mean $\exists b \in \mathbb{Z}$, such that $$ax-1 = bn.$$

(ii) If you are comparing with a linear diophantine equation $$ax+\color{blue}{B}\color{green}y = 1$$ where we know that is has a solution iff $\gcd(a,B)=1$, then the right comparison should be $$ax+\color{blue}n\color{green}{(-b)}=1$$

Note that $a$ and $n$ are given.

If you dislike $-b$ explicitly, you can let $c=-b$ and we have $$ax+\color{blue}n\color{green}{c}=1$$

(iii) hmm... it means $a-1$ is a multiple of $n$. If you started from $$ax\equiv 1 \pmod{n}$$ and you found that $a\equiv 1 \pmod{n}$, then we know that $x \equiv 1 \pmod{n}$ is a solution to the equation.

Remark:

$\exists b \in \color{red}{\exists} Z$, I don't quite understand the second exists statement.