Prove: If $\ a^2$ is a multiple of $\ n$ then $\ a$ is a multiple of by $\ n$ assuming n is prime

Question

How would I prove: If $\ a^2$ is a multiple of $\ n$ then $\ a$ is a multiple of $\ n$. When n is prime. So far all I have

$\ a^2=xn$ where x is any integer, thanks for the help

Answer 1

Consider the prime decomposition of a.
Say $a=(p_1)(p_2)(p_3)*...*(p_k)$.

Thus, $a^2 = (p_1)(p_1)(p_2)(p_2)(p_3)(p_3)*...*(p_k)(p_k)$.

If $a^2$ is div by n, AND n is prime, then n must be equal to one of the primes in the decomposition ($p_1$ through $p_n$). Otherwise, n would be a product of two or more primes, and therefore composite, violating the terms of the problem.

Since $a=(p_1)(p_2)(p_3)...(p_k)$, it necessarily follows that a is divisible by n as well.

Answer 2

That is not true.

For example, $9|6^2$ but $9|6$ is not true.

However, if $n$ is prime then it's always true.

Answer 3

A proof without the prime decomposition:

Let $\;E=\{n\in\mathbf N^*\mid p \text{ divides }na \}$. $E\ne\varnothing$, since it contains $a$ by hypothesis. Hence it has a smallest element $n_0$.

Claim: $n_0$ divides all numbers in $E$.

Indeed, suppose it doesn't, and let $m$ be one not divisible by $n_0$. The Euclidean division of $m$ by $n_0$ yields $$m=n_0q+r,\quad 0<r<n_0.$$ However this implies $ra=ma-qn_0a$ is divisible by $p$ since $m, n_0$ are in $E$. But $r<n_0$, which contradicts the minimality of $n_0$.

As a consequence, $n_0$ divides $p$, so

• either $n_0=1$, which means $p$ divides $1\cdot a=a$,
• or $n_0=p$, which means $p$ divides $a$ since $a\in E$.

Answer 4

This is nothing but a special case for the following theorem:

Assume that $a_1,a_2,\cdots,a_n$ are $n(n \geq 2)$ positive integers and $p$ is a prime. If $p|a_1a_2\cdots a_n$, then at least one within $a_1,a_2,\cdots,a_n$ could be divisible by $p$.