# Simple proof that if $a^2$ is divisible by a prime $b$ then $a$ is divisible by $b$. [duplicate]

I know it's obvious that if $a^2$ is divisible by $b$, given that $b$ is prime ,then $a$ is divisible by $b$. Is there any way to prove this without going into the fundamental theorem of arithmetic? I was told it can be proved starting from the fact that every number is the product of distinct primes, but is there a simpler way?

## marked as duplicate by Dietrich Burde, user147263, graydad, Krish, Jonas MeyerApr 3 '15 at 15:08

• This is not true. Take $a=6$ and $b=36$. – Dietrich Burde Apr 3 '15 at 9:31
• I assume you meant to say that $b$ is prime? – Winther Apr 3 '15 at 9:37
• Yes, I did, my mistake. – user124862 Apr 3 '15 at 9:37
• Any proof of this statement will have to touch upon the fundamental theorem of arithmetic in some way or another (directly or indirectly by using a lemma that builds on the funamental theorem). – Winther Apr 3 '15 at 9:51
• @DietrichBurde i don't think that's the same question. – punctured dusk Apr 3 '15 at 10:38

This could be another expression of Euclids lemma, which states that if $p$ is a prime and divides the product $ab$, then $p$ divides $a$ or $p$ divides $b$. Hence if $p$ divides $a\cdot a$ then $p$ divides $a$.

It is true. Here is a proof without prime decomposition, using only the euclidean division and the definition of a prime number, along the lines of a proof I gave of Euclid'slemma.

Let $E=\bigl\{x\in\mathbf N^*\:;\: b\mid xa\bigr\}$. $E$ is a non-empty subset of $\mathbf N$, since $a$ and $b$ belong to $E$.Hence it has a smallest element, $x_0$.

Claim: $x_0$ divides all elements in $E$.

Indeed, let $x\in E$. The euclidean division by $x_0$ gives $\, x=qx_0+r$ for some $q, r$ ($0\le r<x_0$). Now $b$ divides $xa$ and $x_0a$ by hypothesis, hence it divides $(x-qx_0)a=ra$, which means $r\in E$, unless $r=0$. As $x_0$ is the smallest element in $E$, $r$ can't be in $E$, thus $r=0$, and $x_0$ divides $x$.

In particular, $x_0$ divides $b\,$; as $b$ is prime, $x_0=0$ or $x_0=1$.

• If $x_0=b$, this implies $b$ divides all elements in $E$, amongst which $a$.
• If $x_0=1$, the definition of $E$ implies $b$ divides $1\cdot a=a$.