4
$\begingroup$

This might seem like a trivial question, but I am not very good at mathematics. If I am supposed to show that:

If $p$ is prime show that $p\mid a^2 \implies p\mid a$

I would do like this (I do not even know if it is a valid way to show the statement);

If $p$ is prime then $p\mid p$. So if $p\mid a^2$ it means that $a^2$ must have at least one factor $p$ such that $p\mid a^2$ and due to the fact that $a^2 = a \times a$, it follows that $p = a$. Thus $p\mid a$.

But that is not a formal proof, right? It is more like an informal proof. So my question is if there is a more formal approach to show that:

If $p$ is prime show that $p\mid a^2 \implies p\mid a$

I know that there exist different methods to show divisibility, but due to the obviousness of the statement I have a very hard time showing the statement without using a lot of words.

$\endgroup$
  • $\begingroup$ Bezout's identity? $\endgroup$ – астон вілла олоф мэллбэрг Sep 6 '16 at 11:27
  • 1
    $\begingroup$ What is your definition of prime? This follows directly from the fact that $p$ divides a product if and only if $p$ divides one of the factors. $\endgroup$ – Crostul Sep 6 '16 at 11:28
  • 1
    $\begingroup$ Related: math.stackexchange.com/questions/1910782/… $\endgroup$ – Watson Sep 6 '16 at 11:29
  • 2
    $\begingroup$ Thought it would be interesting/helpful to the OP to point out that more generally, if $p \lvert ab$ then $p \lvert a$ or $p \lvert b$. Even more generally, if $n \lvert ab$ and $\gcd(a,n) = 1,$ then $n \lvert b.$ This is a result known as Euclid's Lemma and a standard proof using Bezout's identity can be found on Wikipedia. $\endgroup$ – quasicoherent_drunk Sep 6 '16 at 11:44
  • 1
    $\begingroup$ (1). "So if $p|a^2$ then $a$ has at least one factor $p$ with $p|a^2\;$" is a tautology. (2). "Due to $a^2=a\times a$ it follows that $p=a. $" Huh? How did $p$ get to be equal to $a$? What if $p=3$ and $a=6$? $\endgroup$ – DanielWainfleet Sep 6 '16 at 16:22
2
$\begingroup$

A quick proof. Since $\textbf{F}_p=\textbf{Z}/p\textbf{Z}$ is a field, and $a^2=0$ in $\textbf{F}_p$, we have $a=0$ in $\textbf{F}_p$.

$\endgroup$
1
$\begingroup$

Suppose that $p\not\mid a$. Then $p$ is not in the factorization of $a$. Since $a^2$ has the same factors as $a$ with exponents doubled, $p$ is not in the factorization of $a^2$, so $p\not\mid a^2$. Contradiction.

$\endgroup$
1
$\begingroup$

Using the fundamental theorem of arithemtic, $a$ is the unique product of $k$ primes

$$a = \prod_{i=1}^k p_i^{\alpha_i} = p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}$$

Then we can write

$$a^2 = \prod_{i=1}^k p_i^{2\alpha_i} = p_1^{2\alpha_1}p_2^{2\alpha_2} \cdots p_k^{2\alpha_k}$$

Now if $p\ |\ a^2 = \prod_i p_i^{2\alpha_i}$, then $p$ must be one of the $p_i$ since the prime factorization is unique.

Therefore we have $p\ | \ \prod_i p_i^{\alpha_i} = a$.


Let's apply this to a simple example. Let $p = 3$ and $a = 60$. Then

$$a = 2^2 \cdot 3 \cdot 5 \text{ and } a^2 = 2^4 \cdot 3^2 \cdot 5^2$$

Since $3$ divides $a^2$ we know that $3$ is one of the primes in the factorization of $a^2$. Thus $3$ is also one of the primes in the factorization of $a$ and therefore divides $a$.

$\endgroup$
  • 2
    $\begingroup$ I'm just guessing from what the OP said and wrote, but I'm guessing that OP does not know the "indexed product" symbol, and is even less likely to make sense of the indexed product without bounds on the index. But OP can correct me if I'm wrong. $\endgroup$ – John Hughes Sep 6 '16 at 11:45
  • $\begingroup$ I was writing the same and think it is a short and good answer $\endgroup$ – user354674 Sep 6 '16 at 11:46
  • $\begingroup$ Good enough. Let's see whether OP selects it or corrects my conjecture about level of understanding. $\endgroup$ – John Hughes Sep 6 '16 at 11:49
  • $\begingroup$ @John Hughes you are correct. I do not know the "indexed product" symbol and I cannot say that I understand this argument. $\endgroup$ – notmyrealname Sep 6 '16 at 11:52
  • 4
    $\begingroup$ There is some amount of circularity involved here. The unique factorization theorem is itself dependent on the property of primes that if $p \mid ab $ then either $p \mid a$ or $p \mid b$. $\endgroup$ – Paramanand Singh Sep 6 '16 at 11:59
1
$\begingroup$

Suppose $p \nmid a$ then we know that $p$ and $a$ have no common factor and hence their GCD is $1$. Therefore there are integers $x, y$ with $px + ay = 1$. Now multiplying by $a$ we get $$apx + a^{2}y = a$$ and since $p \mid a^{2}$ we have an integer $n$ such that $a^{2} = np$ and hence $$apx + npy = a$$ or $$p(ax + ny) = a$$ so that $p \mid a$ and we reach a contradiction. It follows that $p \mid a$.

$\endgroup$
  • $\begingroup$ You'll probably want to reference Bézout's identity for your statement. $\endgroup$ – Alexis Olson Sep 6 '16 at 12:05
  • $\begingroup$ @AlexisOlson: I knew this basic result for years without knowing that it had a name. Thanks for reference. $\endgroup$ – Paramanand Singh Sep 6 '16 at 12:07
1
$\begingroup$

An elementary proof, without the fundamental theorem of arithmetic.

This proof only uses $\mathbf N$ being well ordered and its consequence: Euclidean division.

Consider the set $\;E=\bigl\{x\in \mathbf N^*\enspace\text{such that}\enspace p\mid xa\bigr\}$.

This set is not empty, since it contains $p$ and $a$. So it contains a smallest element, $b$.

Claim: $\;b$ divides every element of $E$.

Indeed, let $x$ be any element of $E$. Euclidean division gives equality $\;x=qb+r$, $\;0\le r<b$. As $x$ and $b$ lie in $E$, so does $r$, unless $r=0$. But this is impossible, since $b$ is the smallest element of $E$. Thus, $r=0$, i.e. $b$ divides $x$.

In particular, $b$ divides $p$. As $p$ is prime, this means $b=1$ or $b=p$.

If $b=1$, by definition of $E$, it means $p$ divides $1\cdot a=a$.

If $b=p$, $\;p$ divides $a$ by the claim, since $a\in E$.

$\endgroup$
1
$\begingroup$

If P doesn't divide a, then a=m.p, where m is a non integer rational number. Multiplying a both sides

a^2 = m.a.p

m.a will still be a non integer rational number. Since m has p in denominator and p cannot divide a. So a^2 has non integer quotient when divided by p.

Hence p should divide a, for it to divide a^2.

$\endgroup$
1
$\begingroup$

First of all, if one assumes ring-theoretic definition of prime, this whole exercise is trivial. So, we obviously won't, we will assume that "prime" means positive integer with exactly two divisors in $\Bbb N$.

One needs to be careful not to fall into circularity here, so let me introduce terminology.

  • We will call positive integer $p$ $\Bbb N$-prime if $p$ has exactly two divisors in $\Bbb N$.

  • We will call (integer) $x$ prime if $x\mid ab\implies x\mid a$ or $x\mid b$.

  • We will call $x\in \Bbb Z\setminus\{0,\pm 1\}$ irreducible if $x = ab\implies a =\pm 1$ or $b = \pm 1$.

Thus, we can reformulate your exercise as

Every $\Bbb N$-prime $p$ is prime in $\Bbb Z$.

because we would then have $p|a^2 \implies p\mid a$ or $p\mid a$.


Lemma. $x$ is irreducible in $\Bbb Z$ if and only if $|x|$ is $\Bbb N$-prime.

Proof. Assume that $x$ is irreducible and that $d\mid |x|$ in $\Bbb N$. Then $x = \pm nd$ for some $n\in\Bbb N$, but since $x$ is irreducible, $d = 1$ or $n= 1$, i.e. $d = 1$ or $d = |x|$.

Conversely, if $|x|$ has exactly two divisors in $\Bbb N$, and $x = ab$, then $|a|,|b|\in\{ 1,|x|\}$, but that means that either $a = \pm 1$ or $b=\pm 1$.


In general, we know that every Euclidean domain is unique factorization domain, and also, we know that in UFD $x$ is prime if and only if $x$ is irreducible.

Thus, if we can prove that $\Bbb Z$ is Euclidean domain, then it is UFD, and thus if $p$ is $\Bbb N$-prime, it is irreducible in $\Bbb Z$ by our Lemma, and hence prime, which would finish the proof by the above remark.

Theorem. $\Bbb Z$ is Euclidean domain with Euclidean function $f\colon\Bbb Z\setminus\{0\}\to \Bbb N$, $f(x) = |x|$.

Sketch of proof. Let $a,b\in\Bbb Z$ with $b\neq 0$. For simplicity let us assume that $a,b>0$.

We want to show that there exists $q,r\in \Bbb N$ such that $a = bq + r$ and $0\leq r < b$. Let us define $q = \min\{n\in\Bbb N\,|\, nb > a\} - 1$ (existence of $q$ is guaranteed by well-ordering of $\Bbb N$) and define $r = a - bq$. Then we have $$bq \leq a < b(q+1)\implies 0\leq a - bq < b \implies 0\leq r < b.$$

General case where $a,b$ are not necessarily positive can be deduced from this by playing with absolute value.

Of course, for $a,b\neq 0$, $f(a)\leq f(ab) \iff |a| \leq |ab| \iff 1\leq |b|$ and we are done.

$\endgroup$
  • 1
    $\begingroup$ I like this answer, although in some ways it reminds me of the title of a book I once saw: Mathematics made difficult. :) I like it partly because although it involves many ideas that are probably unfamiliar to OP, it does so in a very clear way, with pointers to explanations of these ideas. $\endgroup$ – John Hughes Sep 6 '16 at 13:41
  • $\begingroup$ I like the reference to Mathematics made difficult :) To be honest, I've never seen the actual formal proof of all this stuff (for $\Bbb Z$, I mean), so I just wrote it from top of my head. Essentially, this all comes down to $\Bbb Z$ being GCD domain, and it might be easier to prove that and avoid the rest of generalities. $\endgroup$ – Ennar Sep 6 '16 at 13:46
0
$\begingroup$

As $p|a^2$ we write $a^2=pb$. As the left hand side is a square, we write $b=pc^2$. Therefore $a^2=p^2c^2\to a=pc$, hence $p|a$.

$\endgroup$
  • 1
    $\begingroup$ That's quite a leap to say $b=pc^2$. $\endgroup$ – mathematician Sep 6 '16 at 11:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.