Various Proofs Regarding Divisors and Properties of Divisors

In summary: I'm sorry, I think I am misunderstanding you. I am saying that the proof assumes that if a and b are coprime then there exist integers m and n such that am+bn=1 is true. Is this valid?Yes, that is a valid assumption. If a and b are coprime, then there exists a Bézout's identity for them, meaning that there exist integers m and n such that am+bn=1.
  • #1
kripkrip420
54
0
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!
 
Physics news on Phys.org
  • #2
kripkrip420 said:
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.
 
  • #3
micromass said:
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.
 
Last edited by a moderator:
  • #4
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.
 
  • #5
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.
 
  • #6
micromass said:
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.
 
  • #7
micromass said:
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/Generalization/RationalRootTheorem.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.
 
  • #8
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
 
  • #9
micromass said:
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?
 
  • #10
kripkrip420 said:
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.
 
  • #11
micromass said:
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.
 
  • #12
kripkrip420 said:
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.
 
  • #13
micromass said:
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.
 
  • #14
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.
 
  • #15
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.
 
  • #16
micromass said:
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?
 
  • #17
kripkrip420 said:
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 :tongue2:
 
  • #18
micromass said:
Haha, no. I don't know very much about physics really. I'm a mathematician. But physics does interest me :tongue2:

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.).
 

1. What is a divisor?

A divisor is a number that divides evenly into another number, meaning there is no remainder. For example, 2 is a divisor of 8 because 8 divided by 2 equals 4 with no remainder.

2. What is the difference between a proper divisor and an improper divisor?

A proper divisor of a number is any divisor that is less than the number itself. An improper divisor is a divisor that is equal to the number itself. For example, the proper divisors of 6 are 1, 2, and 3, while the improper divisors are 6 and 1.

3. How can I determine if a number is prime or composite?

A prime number only has two divisors, 1 and itself. If a number has more than two divisors, it is considered composite. For example, 7 is a prime number because its only divisors are 1 and 7, while 12 is composite because it has divisors 1, 2, 3, 4, 6, and 12.

4. What is the greatest common divisor (GCD) of two numbers?

The GCD of two numbers is the largest number that is a divisor of both numbers. This can be found by listing out all the divisors of each number and finding the largest one they have in common. For example, the GCD of 12 and 18 is 6 because their common divisors are 1, 2, 3, and 6, and 6 is the largest one they have in common.

5. How is the least common multiple (LCM) of two numbers calculated?

The LCM of two numbers is the smallest number that is a multiple of both numbers. This can be found by listing out the multiples of each number and finding the smallest one they have in common. For example, the LCM of 4 and 6 is 12 because their multiples are 4, 8, 12, and 6, 12, and 18, and 12 is the smallest one they have in common.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
  • General Math
Replies
2
Views
3K
  • Precalculus Mathematics Homework Help
Replies
9
Views
2K
  • Linear and Abstract Algebra
Replies
21
Views
8K
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Linear and Abstract Algebra
Replies
23
Views
4K
  • Linear and Abstract Algebra
Replies
1
Views
2K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
17
Views
316K
Back
Top