If a is not relatively prime to n prove modulo property

Question

If $n>1$ is integer and $1\le a \le n$ is integer such that $(a,n)\neq 1$ then prove there exist integer $1 \le b <n $ such that $ab \equiv 0(mod \; n)$

I have tried everything from going to definitions,constructing the the wanted integer from g.c.d .I do not know how to solve this.Hints would be useful as much as full solutions.

Problem comes from Dummit and Foote book on Abstract Algebra,in the exercises after chapers on integers modulo n,exercise 11

I thank you in advance.

Answer 1

Take a look at the circularity of modular arithmetic:

$$ x * n \equiv x * 0 = 0 \mod{n} $$

Since $d = gcd(a,n) \neq 1$, there exists at least this one common divisor $d$.

Now write $a = x * d$ and $n = b * d$, so

$$ a * b = (x * d) * b = x * (d * b) = x * n \equiv x * 0 = 0 \mod{n} $$

Since there is a common divisor, there must also be $b$.

Answer 2

A full solution would take less space than this very phrase, but I'll give you a hint instead.

The only problem is that $b$ is required to be less than $n$. Otherwise, you could just take $b=n$ and have $ab \equiv 0 \pmod n$ for trivial reasons. So, roughly, the problem is that $b$ needs to be small.

OK, how do you find the smallest $b$ such that $ab$ is divisible by $n$? If you have enough experience, you can just write down a formula for $b$ right away. If you don't, try using the heavy artillery. Let's decompose $a$ and $n$ into products of prime numbers: $$ \begin{align*} a &= \prod_p p^{\alpha_p} \\ n &= \prod_p p^{\beta_p} \end{align*} $$ Here $p$ iterates over all prime numbers, $p^{\alpha_p}$ is the highest power of $p$ that divides $a$, and $p^{\beta_p}$ is the highest power of $p$ that divides $n$.

Now, if $a$ isn't divisible by $n$, it is because some prime numbers occur more times in $n$ than they do in $a$. So, if for some prime $p$ we have $\alpha_p < \beta_p$, then we need to multiply $a$ at least by $p^{\beta_p - \alpha_p}$ to compensate for the difference.

By this logic, we can write an explicit formula for the least number $b > 0$ such that $ab$ is divisible by $n$. Here it is: $$ b = \prod_{\alpha_p < \beta_p} = p^{\beta_p - \alpha_p}. $$ Here $p$ ranges only over those primes which don't occur enough times in $a$ (that is, $\alpha_p < \beta_p$).

Finally, this expression for $b$ can be written much easier using the greatest common divisor for $a$ and $n$. Can you figure it out? Hint: if you decompose $(a, n)$ into prime factors, each prime number $p$ will occur there exactly $\min\{\alpha_p, \beta_p\}$ times.

PS: of course, using prime factorization is a bit of an overkill in this problem. It is by far not the shortest path to the solution. On the other hand, it can be a good exercise. If you finish the line of reasoning above, it may well give you some confidence in the future.