Question

(Introductory Real Analysis) I'm trying to show by contraposition that if the square of a number has a certain number as a factor, its root will also have that certain number as a factor. The way I'm tempted to solve this (after taking the contrapositive of the above statement) is by using a not equal sign, but I'm not sure I understand the mechanics of it. Math below shortly.

Answer 1

Contrapositive of the above:

\[\text{If n is not a factor of} \ a, \ \text{then n is also not a factor of} \ a^2.\]

\[a \neq nk;\]\[a^2 \neq n^2k^2\]

Answer 2

I'd like to treat a not equals sign as a relationship that is maintained under normal algebraic operations, e.g. if you manipulate both sides in the same way, the relationship of "not holding"...will still hold. I don't know if I can do this, though.

Answer 3

Are we assuming \(a\in \mathbb{Z}\)?

Answer 4

I'm trying to do this specifically by contraposition, but we can do that, too, if we're doing what I think we're doing.

And I don't think it should matter for this problem, I think a is an element of either Z or R.

I don't totally understand the implications of what you wrote, I'm taking a minute to think about it.

Answer 5

Well, to be factor-able...

Answer 6

the term, "factor", tells us that \(a\in \mathbb{Z}\)

Answer 7

Yeah, this is actually just a lemma I'm having to prove in the middle of another problem to complete the whole problem; the original prompt doesn't specify the set the value is in, but the original problem itself is proving that sqrt(3) is irrational; I did it by contradiction, so within the context of a proof by contradiction, I should be assuming that sqrt(something) is rational, if that's sensible/correct?

Answer 8

And yeah, a in this context is supposed to be part of a ratio of two integers in lowest terms, so it definitely belongs to Z. Had to think that through for a minute, sorry, lol.

Answer 9

There is an easier way.

Answer 10

\(\mathbb{Z}\) is the set of integers
\(\mathbb{Q}\) is the set of ratio numbers (rational)

Answer 11

the phrase "factor of a rational number" makes no sense

Answer 12

factor must refer to integer
\(a\) must be an integer, then only we can talk about its factors/divisors

Answer 13

Well, at least for proving the a^2 factor part (I brought it to my prof), I have to do that by contraposition, but I'd ideally like to learn any and all ways to solve this.

In any case, I hate to be like, "bluh, this is semantics", but I think we're on the same page regarding what the rationals/integers are, I'm just being really imprecise with my language and throwing stuff together quickly to try and solve this.

Answer 14

Yes, and a is an integer. No disagreement there. But it's both an integer and rational, right?

Answer 15

all integers are rational
whats exciting about that haha

Answer 16

And you have to assume both for the problem-right? You have to assume that a and b are integers since it's a ratio of two integers that makes a rational number that you're assumign sqrt(something) is equal to for the sake of contradiction.

Nothing, but you said that "factor of a rational number" doesn't make sense, but it does, doesn't it? Integers are rational numbers, and they have factors. Even in lowest terms. It's trivial, but it's not wrong, and that wasn't the point, in any case. People were asking me questions regarding what set the variable we're concerned with was in, and I was answering them. It's not really that important right this very moment, but I was just trying to answer questions I was asked so we could move on.

Answer 17

Suppse \(\sqrt{3}=\frac{a}{b}\) where \((a,b)=1\).

Then \(3=\frac{a^2}{b^2}\implies b^2*3=a^2\) from here you may conclude that \(a^2,b^2\) are both odd.

Suppose \(b^2\) was even, then so is \(3b^2\) and then so is \(a^2\) so that we must have \(a,b\) are both even contradiction \((a,b)=1\)

So \(a^2,b^2\) are both odd, so that \(a,b\) are both odd.

So \(a=2k+1\\ b=2k_0+1\) now plug this in,

\(3b^2=a^2\implies 3(4k^2+4k+1)=4k_0^2+4k_0+1\\\implies 6k^2 + 6k + 1 = 2(k_0^2 + k_0).\) The left is odd, the right is even. Yikes!!!

Answer 18

\((a,b)=1\) just means that \(\frac{a}{b}\) CAN'T be reduced any further.

Answer 19

^Part of what I'm not on board with with this/would need to be proved is this: http://i.imgur.com/8kyErQo.png

I'm aware that the square of an odd number is odd, and the square of an even number is even, but I don't know how we can conclude that both a^2 and b^2 themselves are odd.

Answer 20

What I'd conclude from 3b^2=a^2 is that 3 is a factor of a^2. I don't yet know, however, how I can demonstrate that both a^2 and b^2 are odd.

Answer 21

Ok well you also must conclude that \(a^2\) has the same parity as \(b^2\) right?

Answer 22

Wait wait wait, sorry, lol. One minute. I scanned it the first time you posted it, my bad.

Answer 23

forget what I just posted, I thought you had another problem.

Answer 24

back to your issue.

You agree that if \(b^2\) is even then so is \(a^2\) right?

Answer 25

because \(a^2=3*\)even

Answer 26

Yeah.

Answer 27

Ok so let us assume they are both even, then you also agree that if \(a^2\) is even, then so is \(a\)?

Answer 28

But we don't know that b^2 is even. (Nevermind, assumption) And yeah, agreed that if a^2 is even, so is a.

Answer 29

They must either be both even or both odd. I will assume they are both even and show you that that cant be the case. there for they must both be odd. Make sense?

Answer 30

Alright, yeah.

Answer 31

OK so if \(a^2,b^2\) is even, then so is both \(a,b\) and then re can reduce our fraction \(\frac{a}{b}\) right?

Answer 32

re=we

Answer 33

Yeah.

Answer 34

But we assumed at the start that our fraction was reduced so this is a contradiction.

Answer 35

So \(a^2,b^2\) are both odd.

Answer 36

p.s. this proof got a dude killed :)

Answer 37

Maybe the smiley was too much

Answer 38

Oh, I heard about that! What's his name, the dude who the Pythagoreans killed for disclosing it when they wanted to keep it a secret. And yeah, I get it now, at least I certainly get the proof that a and b must both be odd. Now I'm going to re-read the above, one sec.

Answer 39

Well they did not want him to show the world that there were irrational numbers because they thought the world of integers and really did not like that idea. So death ... they also did not allow an open flame next to a mirror...goes to show what they know.

Answer 40

I'm just figuring out the last bit of algebra, but it at the very least conceptually makes sense to me...thanks very much.

Answer 41

the algebra will be easy. np.

Answer 42

Yeah, I don't understand what the heck you did at the very end, it literally just looks wrong, so let me write this out step by step and confirm I'm not crazy:

Answer 43

the starting question is not proved yet :)

Answer 44

since n can be any natural number, and not n=3

Answer 45

lol omg. actually what we proved has nothing to do with the starting question. The starting question is a result of going a different rout that is not needed.

Answer 46

\[3(4k^2+4k+1)=4k_0^2+4k_0+1\](I'm on board with this)
\[12k^2+12k+3=4k_0^2+4k_0+1\]\[12k^2+12k+2=4k_0^2+4k_0\]\[6k^2+6k+1=2k_0^2+2k_0\]
Alright, so this is effectively the same results-I just don't know...how you did your wizard algebra to end up with a different simplification.

Answer 47

I did the exact same thing. I just skip steps...

Answer 48

You had a slightly different written end result, promise. You had plus one on the RHS, which is why I was really confused. Both sides had a plus one, guessing it was a typo. Either way, this makes sense now, heh.

Answer 49

Whoah, hey there, lol. I like hearing everybody here talk. ;_;

Answer 50

It was a personal jab at him, just playin.

Answer 51

You are right :)

Answer 52

a good idea would be if you answer to the actual question :)
@zzr0ck3r

Answer 53

read man, we covered all of this...

Answer 54

ooooooOooo shots fired

Answer 55

Or tell us again how \(n\) might not be \(3\)....

Answer 56

I tell you that chemistry is not physics, as you wrote yesterday, lol! :)
@zzr0ck3r

Answer 57

This dude follows me to other questions and trys to but in and ALWAYS says the wrong thing. Then I show him why he was wrong, as I did here, he then moves on to something else.

What you are referring to is someone asking a chem question in the math section and saying the reason was because people would not answer it is physics. I told the user that people were not answering because his question was chem, not physics.

Just read @Michele_Laino , you might then actually know what you are talking about more.

Answer 58

So at least for the original question, for n=3, we're good, right? We proved all the lemmas necessary in between about how both a and b must be odd, and provided a contradiction showing that sqrt(3) is irrational, but how could we show that if a^2 has a factor alpha, then a also has a factor alpha.

The last thing I'm concerned with (and I'll open up a different question if people would like) is just figuring that out.

Answer 59

Ahh I did not read that post correcty. I did not know the number was a square... sorry. this is true then.

Answer 60

I like one line proofs
in number theory below is a legitimate proof for showing\(\sqrt{3} \not\in \mathbb{Z}\) :

suppose \(\sqrt{3}\) is rational, then for some \(a,b\in \mathbb{Z}\) we have
\[\frac{a}{b} = \sqrt{~3~} \implies \left(\frac{a}{b}\right)^2 = 3 \implies 3b^2 = a^2 \]
By euclid lemma, \((a,b)=1 \implies 3\mid 1\), contradiction \(\blacksquare\)

Answer 61

much nicer

Answer 62

I think we still need to show \((a^2, b^2)=1 \iff (a,b)=1 \)

Answer 63

**
I like one line proofs
in number theory below is a legitimate proof for showing\(\sqrt{3} \not\in \color{red}{\mathbb{Q}}\) :

suppose \(\sqrt{3}\) is rational, then for some \(a,b\in \mathbb{Z}\) we have
\[\frac{a}{b} = \sqrt{~3~} \implies \left(\frac{a}{b}\right)^2 = 3 \implies 3b^2 = a^2 \]
By euclid lemma, \((a,b)=1 \implies 3\mid 1\), contradiction \(\blacksquare\)

Answer 64

Wait a minute, I don't understand, what did we still need to show? Up to the point I thought I was done, what else did we need to prove?

Answer 65

we're done!im talking about my proof in the end... it has nothing to do with zzr
his proof is complete

Answer 66

you are done, this is a different method.

But you need euclids lemma for this version

Answer 67

Number theorist like to make things easy.... pfft

Answer 68

jk :) this one is much "nicer"

Answer 69

Alright. The last thing I'd like to double down on again is that I want to prove that a factor of a^2 is also a factor of a, and I'd like to do that doing contraposition, but I don't know how to go about doing that.

Solving one problem in as many ways possible is right now pretty important to me so that I develop a sense of the different ways of solving problems, not just getting the solution.

Answer 70

The best proofs are one liners.

Here is my favorite proof that the identity element is unique in a group.

\(e_1=e_1*e_2=e_2\)

Answer 71

Can I see how you are using this in the proof that \(\sqrt{3}\) is irrational?

Answer 72

(Hell, that *was* my original question. I was focusing on that lemma which ended up never getting answered, but the larger question getting answered in a different way.)

@zzr0ck3r , sure. One minute.

Answer 73

How do you guys put (not LaTeX text) plaintext in line with math in openstudy comments, by the way?

Answer 74

`\(\text{like this}\)`

Answer 75

Actually I am using that in my proof above while making the jump :
\((a^2,b^2)=1 \implies (a,b)=1\)

Answer 76

This is some number theory stuff, @ganeshie8 will love to do it :)

Answer 77

Ah, I would go a different rout for that.

Answer 78

if some number divides a and b then surely it divides a^2 and b^2...

Answer 79

1.) Assume sqrt(3) is rational (proof by contradiction.)
\[\text{If} \ \sqrt{3} \ \text {is rational, then} \ \sqrt{3}=\frac{a}{b}, \ \ \ a,b,\in \mathbb{Z}\]\[3=\frac{a^2}{b^2}\]\[3b^2=a^2\]
@zzr0ck3r Yeah, but I want that to be proven deductively, lol, not just going "lol it's obvious".

If a^2=3b^2, 3 is a factor of a^2. If b is already assumed as an integer, its square will also be an integer (here's where this lemma is necessary).\[3b^2=a^2 \rightarrow 3b^2=(3 \gamma)^2=9 \gamma^2\]

Answer 80

\[3b^2=9 \gamma^2\]By the same logic, 3 is a factor of b^2. By the same lemma as before, if 3 is a factor of b^2, it must be a factor of b. Thus, b=3(delta), where delta is some integer.

Putting these into the original expression a/b shows you that they were not, as assumed, in lowest terms. This is the contradiction that shows you that sqrt(3) is not rational.

Answer 81

And Ganeshie, I actually have no idea what that notation means in your last post/how would that be read in words?

Answer 82

\((a, b)\)

is read as

\(\gcd\) of \(a\) and \(b\)

Answer 83

But yeah, that's why I'm trying to prove-by contraposition-that if a^2 has some root, a must also have it in common.

Ah.

Answer 84

first:
I don't follow you, since I have no reason
second:
what I write is correct,
furthermore, what I saw is that you are very adept at distorting the truth and in offending others, and less capable in doing mathematics, it is clear that your parents have not been able to teach good manners.
@zzr0ck3r

Answer 85

Guise pls.

Answer 86

i smell the mathematician vs physicist fight

Answer 87

@ganesh he started to offend me as you can see from the above replies

Answer 88

I promised to Mrs. Preetha that I would not fight with that person, but he continues to offend me

Answer 89

...I just want to get my original question answered. Could this please be done somewhere else. I still haven't figured out the question I first asked and was first and foremost was concerned with, everyone sort of ignored that, went, "No, I have a better method" and did whatever they felt like.

Which is cool, but I still don't understand how to do this in this specific way that I'm concerned with.

Answer 90

right! In fact I wrote that the starting question is not proved yet @Mendicant_Bias and @zzr0ck3r started to offend me

Answer 91

` if the square of a number has a certain number as a factor, its root will also have that certain number as a factor.`

is equivalent to showing :
if the \(\gcd(a^2,b^2)\) is \(d^2\), then the \(\gcd(a,b)\) is \(d\)

Answer 92

lets try proving the latter statement..

Answer 93

...What? Alright, hold off, I didn't try to offend you at all. I didn't say a word to you. I don't have an issue with you.

Answer 94

Don't bring me into this. Anyways, yeah, let's try proving that.

Answer 95

@Michele_Laino

again, simply read

" but I'd ideally like to learn any and all ways to solve this." -TheQuestionAsker

just read man, read.

Answer 96

Alright, so I have no idea how to compare those two statements off the top of my head, hmm...

Answer 97

do you have teamviewer/skype ?