Register to reply

Various Proofs Regarding Divisors and Properties of Divisors

by kripkrip420
Tags: divisor, factor, number theory, proof
Share this thread:
kripkrip420
#1
Apr13-12, 04:34 PM
P: 54
Hello there. I have been reading G.H. Hardy's book "A Course of Pure Mathematics". It is a fantastic introduction to Analysis. I have no problems with the book so far, however, it does assume some knowledge in number theory. I just want to make sure that the following proofs for properties of numbers are done correctly and that there is no apparent logical flaw in them. Thank you for your critisism (if any).

Proposition 1:

If α divides β, then α divides β[itex]^{η}[/itex], where α and β are integers and η is a positive integer.

Proof:

If α divides β then (by definition) there exists some integer κ such that ακ=β.

Raising both sides of the above equation to η yields the following;

(ακ)[itex]^{η}[/itex]=β[itex]^{η}[/itex].

By use of the laws of exponents, we get

α[itex]^{η}[/itex]κ[itex]^{η}[/itex]=β[itex]^{η}[/itex].

We can then express α[itex]^{η}[/itex] as α*(α[itex]^{η-1}[/itex]).

Thus,

α*(α[itex]^{η-1}[/itex])=β[itex]^{η}[/itex]

and we have shown that α divides β[itex]^{η}[/itex].

Proposition 2:

This proposition was the opposite of the above propostion. It states that if α divides β[itex]^{η}[/itex] then α divides β.

The proof was done as an extremely simple contrapositive I'm sure you all can figure out.

Proposition 3:

Show that if α and β are coprime, then so are α and β[itex]^{η}[/itex], where α and β are integers and η is a positive integer.

Proof:

Assume there exists some common factor of α and β[itex]^{η}[/itex], call it ω.

Let α=ωc and let β[itex]^{η}[/itex]=ωd where c and d are integers.

α=ωc→ω=α[itex]/c[/itex].

Thus,

β[itex]^{η}[/itex]=(α[itex]/c[/itex])*d.

The above can be expressed as

β[itex]^{η}[/itex]=αdc[itex]^{-1}[/itex]

and it is clear that α[itex]/β^{η}[/itex].

But, from the preceding proofs, if α divides β[itex]^{η}[/itex], then α divides β. But this contradicts our supposition, since α and β are coprime. Hence, by contradiction, there exists no factor ω shared by both α and β[itex]^{η}[/itex] if α and β are coprime, i.e. α and β[itex]^{η}[/itex] are coprime.

Also, can somebody tell me how to display the "divides" symbol please? Thank you all for your help!
Phys.Org News Partner Science news on Phys.org
Scientists develop 'electronic nose' for rapid detection of C. diff infection
Why plants in the office make us more productive
Tesla Motors dealing as states play factory poker
micromass
#2
Apr13-12, 05:33 PM
Mentor
micromass's Avatar
P: 18,323
Quote Quote by kripkrip420 View Post
Proposition 2:

This proposition was the opposite of the above propostion. It states that if α divides β[itex]^{η}[/itex] then α divides β.

The proof was done as an extremely simple contrapositive I'm sure you all can figure out.
Yeah, I'm sure it was extremely simple. Only sad that the propositon isn't true.
kripkrip420
#3
Apr13-12, 06:57 PM
P: 54
Quote Quote by micromass View Post
Yeah, I'm sure it was extremely simple. Only sad that the propositon isn't true.
Why do you first say "I'm sure it was extremely simple" and then go on to state "only sad that the proposition isn't true"? That makes no sense. The contrapositive I talk of was found online. Assuming that proposition 1 is true, proposition 2 can be "proven" as follows.

Assume α does not divide β, then it does not divide β[itex]^{η}[/itex] (by the first proposition).
Therefore, in order for α to divide β raised to n, it must divide β.
If you have an example of were this is not the case, please share. I know the proof is not very rigorous at all but I am mainly interested in the truth value of proposition 3. If the last two propositions are wrong, please state where and why they are wrong and offer a proof of proposition 3. Thank you.

micromass
#4
Apr13-12, 07:05 PM
Mentor
micromass's Avatar
P: 18,323
Various Proofs Regarding Divisors and Properties of Divisors

Your use of the contrapositive isn't justified.
The contrapositive of proposition 1 would be

"If α does not divide βn, then α does not divide β"

You somehow took the converse of that statement, which is not true.
Robert1986
#5
Apr13-12, 07:08 PM
P: 828
You asked for criticism. You didn't give a proof of the proposition, what could micromass have said?

I'm not reading your proof. Here is a counter example: 4 divides 36 (6^2) but not 6.
kripkrip420
#6
Apr13-12, 07:13 PM
P: 54
Quote Quote by micromass View Post
Your use of the contrapositive isn't justified.
The contrapositive of proposition 1 would be

"If α does not divide βn, then α does not divide β"

You somehow took the converse of that statement, which is not true.
I apologize. I did not look at the definition of contrapositive. Again, I found the "proof" online and wanted to move quickly in proving proposition 3. I assumed converse and contrapositive were equal. My mistake. I will post a proof of proposition 3 in a moment obviously without the use of proposition 2. I thank you both for your help. Also, I am not angry, I simply don't like it when others are sarcastic. Tell me that I'm a moron for believing the internet and not testing the proof myself. I'd much rather read that. Thank you again.
kripkrip420
#7
Apr13-12, 08:13 PM
P: 54
Quote Quote by micromass View Post
Your use of the contrapositive isn't justified.
The contrapositive of proposition 1 would be

"If α does not divide βn, then α does not divide β"

You somehow took the converse of that statement, which is not true.
Hello, I found the following proof on a website for proposition 3.

http://www.cut-the-knot.org/Generali...tTheorem.shtml

When the proof is completed it states "so a and bc are coprime". Now I noticed that what was done was a factorization of the expression in the form an+bm=1 to show that a and bc are coprime. However, it seems that the proof assumes the converse of "If a and be are coprime then there exist integers m and n such that am+bn=1", is true. I assume this is the case because the proof shows a(expression 1)+(expression 2)bc=1. And since the entire expression is in the form of am+bn=1 then it is assumed that a and bc are coprime (the converse of the original statement). Is this an accurate example of converse and is it a valid assumption to be made without explicit reference? Thank you and I apologize for calling you a buffoon.
micromass
#8
Apr13-12, 08:20 PM
Mentor
micromass's Avatar
P: 18,323
Yes, in general for a and b is true

a and b are coprime if and only if there exist m and n such that am+bn=1.

But you do need to prove both sides of the equivalence. Just saying that "this is the converse" is not good enough.

But the implication from right to left is easy enough. Take d such that d divides both a and b. Then d divides am+bn. Thus d divides 1. It follows that d=1 or d=-1, so a and b are coprime
kripkrip420
#9
Apr13-12, 08:32 PM
P: 54
Quote Quote by micromass View Post
Yes, in general for a and b is true

a and b are coprime if and only if there exist m and n such that am+bn=1.

But you do need to prove both sides of the equivalence. Just saying that "this is the converse" is not good enough.

But the implication from right to left is easy enough. Take d such that d divides both a and b. Then d divides am+bn. Thus d divides 1. It follows that d=1 or d=-1, so a and b are coprime
Okay. Thank you very much! I realize that saying it is not enough. I was just wondering why the site did not move forward in showing that the converse was in fact true. Is it considered acceptable to not state such a thing in a proof that relies on such an argument?
micromass
#10
Apr13-12, 08:35 PM
Mentor
micromass's Avatar
P: 18,323
Quote Quote by kripkrip420 View Post
Okay. Thank you very much! I realize that saying it is not enough. I was just wondering why the site did not move forward in showing that the converse was in fact true. Is it considered acceptable to not state such a thing in a proof that relies on such an argument?
It's acceptable in advanced books. But I think the site should have given a proof.

But now you saw such an argument, you can easily construct one yourself.
kripkrip420
#11
Apr13-12, 08:40 PM
P: 54
Quote Quote by micromass View Post
It's acceptable in advanced books. But I think the site should have given a proof.

But now you saw such an argument, you can easily construct one yourself.
Thank you again. Now, I have a few final questions. Forgive me for bothering you but I have no guidance. I notice that in a lot of these books, a lot of knowledge in other fields of mathematics is assumed. I am not yet in university and I have no structure in the subject or an order in which to learn it. I tend to find that I pick up a book, get through the first few chapters, and then become stuck because it has moved past my realm of knowledge. Is there any sort of path that you would personally recommend when in pursuit of the study of mathematics? Thank you again. You have been very helpful.
micromass
#12
Apr13-12, 08:42 PM
Mentor
micromass's Avatar
P: 18,323
Quote Quote by kripkrip420 View Post
Thank you again. Now, I have a few final questions. Forgive me for bothering you but I have no guidance. I notice that in a lot of these books, a lot of knowledge in other fields of mathematics is assumed. I am not yet in university and I have no structure in the subject or an order in which to learn it. I tend to find that I pick up a book, get through the first few chapters, and then become stuck because it has moved past my realm of knowledge. Is there any sort of path that you would personally recommend when in pursuit of the study of mathematics? Thank you again. You have been very helpful.
Sure I can recommend a path. But a lot depends on what exactly you aim to study and what exactly you know already. So if you tell me that, then I can recommend you a good path.
kripkrip420
#13
Apr13-12, 08:51 PM
P: 54
Quote Quote by micromass View Post
Sure I can recommend a path. But a lot depends on what exactly you aim to study and what exactly you know already. So if you tell me that, then I can recommend you a good path.
Well, what I have applied to is a double major in Mathematics and Physics. I want to become a theoretical physicist as I have a great passion for the study of nature. However, that said, I also very much enjoy pure mathematics. My knowledge in the area of mathematics extends through elementary algebra and calculus. Neither of the courses I took were very rigorous as they were high school courses. I have little knowledge in analysis and have some knowledge in naive set theory. I would essentially like to start from "the ground up" but in a more rigorous sense. I know that, as a physicist, I won't be required so much to know proofs as I will be to apply theorems, but that bothers me. I need to have a fundamental understanding of WHY something works and if it REALLY is TRUE. I guess I should probably read Euclid's Elements since it comes up in a lot of proofs. Thank you. If you need me to be more elaborate, I will try to explain myself better.
micromass
#14
Apr13-12, 08:59 PM
Mentor
micromass's Avatar
P: 18,323
I think the first thing you need to do now is to get a rigorous understanding of calculus. I suggest you work through the calculus book of Spivak. Be alarmed: the exercises in this book are NOT easy. But the book is still very good and I certainly recommend it.

At the same time as studying calculus, you should take a look at linear algebra. Books like the one by Friedberg are very good introductions. Another good book is by Serge Lang.

After that, you might want to do multivariable calculus and abstract algebra.

Once you did calculus and linear algebra, the door is open to more exciting math. Doing a book like Spivak is an excellent preperation for a real analysis course. But you can also do things like differential geometry.

But first things first, try to get acquainted with calculus and linear algebra first.
micromass
#15
Apr13-12, 09:03 PM
Mentor
micromass's Avatar
P: 18,323
About Euclid. Euclid's elements is a really neat book. But I don't recommend you to actually read it. You will not need it much in your academic carreer, and what you do need will be explained in modern books.

It's still a nice book with many fun propositions, but it won't be that useful to you to read it now.
kripkrip420
#16
Apr13-12, 09:11 PM
P: 54
Quote Quote by micromass View Post
I think the first thing you need to do now is to get a rigorous understanding of calculus. I suggest you work through the calculus book of Spivak. Be alarmed: the exercises in this book are NOT easy. But the book is still very good and I certainly recommend it.

At the same time as studying calculus, you should take a look at linear algebra. Books like the one by Friedberg are very good introductions. Another good book is by Serge Lang.

After that, you might want to do multivariable calculus and abstract algebra.

Once you did calculus and linear algebra, the door is open to more exciting math. Doing a book like Spivak is an excellent preperation for a real analysis course. But you can also do things like differential geometry.

But first things first, try to get acquainted with calculus and linear algebra first.
Okay. Sounds good. Thank you very much and thanks for the wonderful recommendations for books. By the way, I like your remake of Oppenheimer's quote (or rather, the Bhagavad Gita).

Is it safe to assume that you are either a physicist, a physicist in progress, or a polymath?
micromass
#17
Apr13-12, 09:13 PM
Mentor
micromass's Avatar
P: 18,323
Quote Quote by kripkrip420 View Post
Okay. Sounds good. Thank you very much and thanks for the wonderful recommendations for books. By the way, I like your remake of Oppenheimer's quote (or rather, the Bhagavad Gita).

Is it safe to assume that you are either a physicist, a physicist in progress, or a polymath?
Haha, no. I don't know very much about physics really. I'm a mathematician. But physics does interest me
kripkrip420
#18
Apr13-12, 09:24 PM
P: 54
Quote Quote by micromass View Post
Haha, no. I don't know very much about physics really. I'm a mathematician. But physics does interest me
How can one have Physics without Mathematics? Love them both. Thank you again for your help and (perhaps more importantly) your time. As I read through Spivak's book, I will likely find myself on this wonderful site once again. I hope we bump into each other (in whatever ways one could "bump" into another over the internet) again. Thank you micromass (by the way, almost everything on this site suggests that you have a background in physics such as your name and signature. I understand now why it is foolish to assume.).


Register to reply

Related Discussions
Intro to Proofs: Greatest Common Divisors Calculus & Beyond Homework 2
I tried with comparing highest exponents Linear & Abstract Algebra 1
Some proofs involving greatest common divisors Precalculus Mathematics Homework 1
Proofs Involving Greatest Common Divisors Precalculus Mathematics Homework 6
Find all divisors of for example 29601 Linear & Abstract Algebra 3