0
$\begingroup$

The full question is:

Let $a$ and $n$ be positive integers and let $d = \gcd(a, n)$. Show that if $\bar{a}$$\bar{x}$ = $\bar{1}$ has a solution for $x$, then $d = 1$.

My approaching is: Since $\gcd(a,n) = d$, $d$ is the smallest positive integer that can be written as

$$ax + ny = d \text.$$

Assume that the function is modulo $n$, then we have:

$(ax + ny) \mod n = d \mod n$

Hence $(1 + ny) \mod n = d \mod n$

$(1 + 0) \mod n = d \mod n$

$1 = d$

Please correct me if I'm wrong. Thank you.

$\endgroup$
2
  • $\begingroup$ What does the bar notation mean? $\endgroup$ Commented Feb 8, 2018 at 6:42
  • $\begingroup$ @user_194421 The bar notation means the equivalence class modulo a number (most of the time n) and a is just an integer. $\endgroup$
    – JTJung
    Commented Feb 8, 2018 at 6:47

1 Answer 1

2
$\begingroup$

Only with $d\equiv1\pmod n$ you can't conclude that $d=1$. You should mention that since $d$ is a positive divisor of $n$, $1\le d\le n$.

There is another more serious fault. You use Bezout's identity to write $$ax+by=d$$ and then you assume that this same $x$ is the solution of $\bar a\bar x=\bar 1$.

My approach:

Since $\bar a\bar x=\bar 1$, that is, $$ax\equiv 1\pmod n,$$ there is some $y\in\Bbb Z$ such that $$ax-1=yn$$ or $$ax-yn=1$$

Now, if $d$ is a positive, common divisor of $a$ and $n$, say $a=a'd$, $n=n'd$, we have $$d(a'x-yn')=1$$ so $d$ divides $1$. This implies $\gcd(a,n)=1$.

$\endgroup$
2
  • $\begingroup$ So if I can't assume there is the same x, how can I improve my solution? $\endgroup$
    – JTJung
    Commented Feb 8, 2018 at 6:51
  • $\begingroup$ Great, I understand this now. Thank you so much. $\endgroup$
    – JTJung
    Commented Feb 8, 2018 at 15:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .