Suppose $a,b,m,n$ are natural numbers, prove that if $a({m \over n})=b$ and $(a,n)=1$, then ${m \over n} \in \mathbb{N}$ [closed]

Suppose that $a,b,m,n$ are natural numbers, prove the following statement:

If $a({m \over n})=b$ and $(a,n)=1$, then ${m \over n} \in \mathbb{N}$

Solution 1:

If $(a,n)$=1 then we can find integers $x$ and $y$ such that $ax+ny=1$. One way to find these involves performing repeated divisions with remainder, as in Euclid's algorithm for GCD.

If also $am=bn$, then $axm=bxn$, from which $(1-ny)m = bxn$ which is to say $m = (bx-ym)n$. So $m$ is divisible by $n$.

Solution 2:

i.e. $\, (n,a)=1,\ \ n\mid am\ \Rightarrow\ n\mid m\ \,$ in divisibility form (Euclid's Lemma). Below are $3$ proofs:

$\ \smash[t]{\begin{align}\\ \\ nx\!+\!ay=&\,\color{#c00}1,\,\ n\ \mid\ am\ \ \ \Rightarrow\, n\ \mid\ m.\ \ \ {\bf Proof}\!:\,\ n\ \mid\ nm,am\, \Rightarrow\, n\,\mid nmx\!\!+\!amy\! =\, (\!\overbrace{nx\!+\!ay}^{\large\color{#c00} 1}\!) m = m\\ (n,\ \ \ a)=&\,\color{#c00}1,\,\ n\ \mid\ am\ \ \ \Rightarrow\, n\ \mid\ m.\ \ \ {\bf Proof}\!:\,\ n\ \mid\ nm,am\, \Rightarrow\, n\,\mid (nm,\ \ am) = (n,\ \ \ a)\ \ m =\, m\\ N\! +\!A\ =&\,\color{#c00}1,\, N\supseteq AM\, \Rightarrow N \supseteq M.\, \ \ {\bf Proof}\!: N \supseteq\! NM,\!AM\!\Rightarrow N\supseteq NM\!+\!\!AM =(N\!+\!A)M = M \end{align}}$

The first proof uses the Bezout identity. The second instead employs basic gcd laws (notably the distributive law) and works more generally. The third proof is a translation into ideal form.