Math Is Fun Forum

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Proof that all primes are irreducible

I'd just like to clarify something quickly...

We define a prime number p to be an integer greater than 1 such that given integers m and n, p|mn ⇒ p|m or p|n.
We define an irreducible to be an integer t, with the property that t is divisible only by ±t and ±1.

This is the proof as I understand it:

If p is prime and p =mn, then p|mn and so p|m or p|n. If p|m, then m = cp and so p = pcn, and since p ≠ 0 we have cn = 1 and so c = n = 1 or c = n = -1. Hence we have n=±1 ⇒ m=±p for p=mn to be true. A similar argument applies if p|n (namely that m=±1 ⇒ n=±p). In both cases we see that p is only divisibile by ±p and ±1 and is therefore irreducible.

The proof in my book says pretty much the same thing, but after stating that a similar argument can be applied if p|n, it says "hence if m divides p, then m = ± p or ± 1". I find this an odd way of saying it. Is what I've written in the proof above correct by itself?

Thanks.

Last edited by Daniel123 (2008-08-11 08:58:22)

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Proof that all primes are irreducible

Your proof is correct.

In fact, it is also true that every irreducible integer > 1 is a prime. This is because the integers

form what’s called a unique-factorization domain (UFD). In general, every prime is an irreducible in any integral domain. The converse, that every irreducible is a prime, is not true in general, but in a UFD it does hold.

Last edited by JaneFairfax (2008-08-11 11:34:40)

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Proof that all primes are irreducible

Brilliant, thanks Jane.

I googled UFD, and can sort of see what's going in a non-technical way. My book says "Later we will show that all positive irreducibles are prime", so I shall wait until I get onto that

Last edited by Daniel123 (2008-08-11 21:56:51)

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Proof that all primes are irreducible

Well, first we define what a unit is. It’s an element that divides the multiplicative identity. In the integers, therefore, the units are 1 and −1.

In a UFD, any element that is not 0 or a unit can be “uniquely factorized”, i.e. written uniquely as a product

where u is a unit and the

’s are irreducibles. Thus, every integer > 1 can be written uniquely as a product of positive irreduciles.

Now let t be a positive irreducible, t > 1, and suppose t divides ab. Thus kt = ab for some integer k. Clearly both a and b are not 0 since t is not 0. If both a and b are units, then t would be a unit, contradicting the fact that t > 1. Thus a or b or both can be uniquely factorized. We can assume WLOG that both a and b are positive, so one or both of them can be written uniquely as a product of positive irreducibles.

If a = 1 and b can be uniquely factorized, say

for positive irreducibles

, then

. By uniqueness of factorization, t must be equal to one of the

’s, say

. Thus

, i.e. t divides b.

Similarly, if b = 1 and

for positive irreducibles

, then t is one of the

’s and so t divides a.

And if both a, b > 1, then

so t must be one of

’s or one of the

’s, and so t divides a or b as before.

Hence t is a prime.

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Proof that all primes are irreducible

I've only just gone back to this book after a while, and I've come across its proof that an irreducible integer is a prime:

Suppose that t is irreducible and that t|mn. Suppose also that t does not divide m. Since the only factors of t are ±1 and ±t, this means that (t,m) = 1. It follows that there exists integers x and y such that xt + ym = 1. Hence xtn + ymn = n. Now t|xtn and t|ymn, and hence t|n. It follows that t is prime.

I have two problems with this.

1. Why is it ok to suppose that t does not divide m?
2. 'Now t|xtn and t|ymn' - don't really see where this comes from, and how it leads to t|n.

Thanks.

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Proof that all primes are irreducible

1.
Because the object is to prove that t divides either m or n. Given any t and m, either t divides m or t doesn’t divide m. If t divides m, the result is already true and there is nothing to prove. So we consider the other case, that t doesn’t divide m. Then, in order for the result to hold, we need to show that t divides n.

2.

because

by assumption. Since

and

Daniel123

Member

Registered: 2007-05-23

Posts: 663

Re: Proof that all primes are irreducible

Ahh I see. Thanks Jane