Various Proofs Regarding Divisors and Properties of Divisorsby kripkrip420 Tags: divisor, factor, number theory, proof 

#1
Apr1312, 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! 



#2
Apr1312, 05:33 PM

Mentor
P: 16,518





#3
Apr1312, 06:57 PM

P: 54

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. 



#4
Apr1312, 07:05 PM

Mentor
P: 16,518

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. 



#5
Apr1312, 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. 



#6
Apr1312, 07:13 PM

P: 54





#7
Apr1312, 08:13 PM

P: 54

http://www.cuttheknot.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. 



#8
Apr1312, 08:20 PM

Mentor
P: 16,518

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
Apr1312, 08:32 PM

P: 54





#10
Apr1312, 08:35 PM

Mentor
P: 16,518

But now you saw such an argument, you can easily construct one yourself. 



#11
Apr1312, 08:40 PM

P: 54





#12
Apr1312, 08:42 PM

Mentor
P: 16,518





#13
Apr1312, 08:51 PM

P: 54





#14
Apr1312, 08:59 PM

Mentor
P: 16,518

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
Apr1312, 09:03 PM

Mentor
P: 16,518

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
Apr1312, 09:11 PM

P: 54

Is it safe to assume that you are either a physicist, a physicist in progress, or a polymath? 



#17
Apr1312, 09:13 PM

Mentor
P: 16,518





#18
Apr1312, 09:24 PM

P: 54




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 