BG-Maths

[Vic]

Totally lost with this discrete math problem.

Use induction to prove that if p is a prime and p | a^n for n > 1, then p | a.

I don't even know what to do for the basis; insert values into all variable or just into n?

Any help would be awesome. Thanks

[Bobbity]

To prove a statement using mathematical induction, you need to show two things: 1.) The statement is true for n=1 (or the lowest n-value specified by the problem). 2.) Given that the statement is true for n=k (k being an arbitrary natural number), then it follows that the statement must be true for n=k+1.

To get you started on the problem, let's define S(n) to be the statement, "If p is prime and p divides a^n, then p divides a." First, we need to show that S(1) is true (or S(2), depending on whether you meant for your inequality to be inclusive).

S(1): If p is prime and p divides a^1, then p divides a.

This is obviously true (since we explicitly stated p divides a^1=a), so we're done with the first step. Now you need to show that if S(k) is true, then it follows that S(k+1) is true. Namely, prove the following:

If p is prime and p divides a^k implies that p divides a, then it follows that the statement "p divides a^(k+1)" also implies that p divides a.

This part is a little trickier, but in lieu of doing all the work for you, I'll let you try to work on it.

[Vic]

Thanks. Think I got it.

[Trajan]

I wonder why they want you to use induction to prove this, seems like an odd way to prove it imo... It is much easier to just break a down into its prime factorization to prove the problem. Maybe that is just too easy?

[SDSD]

I wonder why they want you to use induction to prove this, seems like an odd way to prove it imo... It is much easier to just break a down into its prime factorization to prove the problem. Maybe that is just too easy?

Probably. If you use the prime factorization, all you're going to do is state a definition and then you're pretty much done.

[joft]

may be building up to a proof of the fundamental theorem of arithmetic, so you don't want to use the result that you're trying to prove in your proof (circular reasoning)

everyone knows what integer prime numbers are, but it's possible to talk about primes in other circumstances as well. a set R which possesses many of the same properties as the integers, such as an associative, commutative addition operation, and a multiplication operation that distributes with addition, etc, is called a "ring." The integers are a ring, but so are the set of all nxn matrices with matrix addition and matrix multiplication. so are the set of all "quadratic numbers" a+sqrt(2)*b where a, b are rational numbers.

so it turns out we can define "prime" elements of any ring, and the definition goes like this: p is a prime if p|(ab) implies p|a or p|b. here's a cool example:

http://en.wikipedia.org/wiki/Gaussian_integer
(there's a picture that shows some of the Gaussian primes in the complex plane)

another nice thing about the integers is that they are a "unique factorization domain," meaning every element has an essentially unique (up to reordering and multiplying by units like 1 and -1) factorization into prime elements. Not all rings are UFDs, but, for example, the Gaussian integers are, or the set of all polynomials (in variable x) with real number coefficients. (example of a prime polynomial in this ring: x^2+1, but if you think of it as a polynomial with complex coefficients then it's no longer prime!)

so if you want to prove some ring (such as the integers) is a UFD, you start with the definition of prime and work your way up. the fact that some rings are not UFDs is an extremely important fact, and it's probably the reason that Fermat believed he had proven his "last theorem" when he probably really hadn't (he probably thought every ring was a UFD).

[Trajan]

I doubt it's building up to a proof of the fundamental theorem of arithmetic, I've proved that before and don't remember using induction. Has been awhile though, so meh...