Prooving a statement with a Lemma


by alexk307
Tags: discrete, math, number theory, proof
alexk307
alexk307 is offline
#1
Mar29-11, 02:32 PM
P: 27
1. The problem statement, all variables and given/known data
Using the lemma below, prove that if two integers divide each other, then they are equal

Lemma: If the product of two integers is 1, then the integers each equal 1.


2. Relevant equations



3. The attempt at a solution
Very lost here, I can format the proof but I don't know where to start it. Also, isn't the lemma false? If a*b = 1, then a and b equal 1. What about 3/4 * 4/3 = 1? or 2/3 * 3/2 = 1?
Phys.Org News Partner Science news on Phys.org
NASA's space station Robonaut finally getting legs
Free the seed: OSSI nurtures growing plants without patent barriers
Going nuts? Turkey looks to pistachios to heat new eco-city
gb7nash
gb7nash is offline
#2
Mar29-11, 04:18 PM
HW Helper
P: 805
Quote Quote by alexk307 View Post
Also, isn't the lemma false? If a*b = 1, then a and b equal 1. What about 3/4 * 4/3 = 1? or 2/3 * 3/2 = 1?
Ah, but you're forgetting the hypothesis of the lemma. What's the hypothesis? The hypothesis is assumed to be true so....

Once you understand the lemma, what does it mean for one integer to divide another integer?
Mark44
Mark44 is offline
#3
Mar29-11, 04:24 PM
Mentor
P: 21,012
Quote Quote by alexk307 View Post
1. The problem statement, all variables and given/known data
Using the lemma below, prove that if two integers divide each other, then they are equal

Lemma: If the product of two integers is 1, then the integers each equal 1.


2. Relevant equations



3. The attempt at a solution
Very lost here, I can format the proof but I don't know where to start it. Also, isn't the lemma false? If a*b = 1, then a and b equal 1. What about 3/4 * 4/3 = 1? or 2/3 * 3/2 = 1?
3/4 and 4/3 aren't integers, nor are 2/3 and 3/2.

alexk307
alexk307 is offline
#4
Mar29-11, 05:43 PM
P: 27

Prooving a statement with a Lemma


Quote Quote by Mark44 View Post
3/4 and 4/3 aren't integers, nor are 2/3 and 3/2.
Oh man, that's embarrassing... Thanks
alexk307
alexk307 is offline
#5
Mar29-11, 06:09 PM
P: 27
okay so,
I assumed that a and b are both integers and that a/b = 1.
Should I also assume that c*d=1 according to the lemma that if cd=1 then c and d are 1?
gb7nash
gb7nash is offline
#6
Mar29-11, 06:12 PM
HW Helper
P: 805
Quote Quote by alexk307 View Post
okay so,
I assumed that a and b are both integers and that a/b = 1.
Should I also assume that c*d=1 according to the lemma that if cd=1 then c and d are 1?
Start with the hypothesis of what you're trying to prove. Using math terms, what does it mean if a divides b? b divides a?
alexk307
alexk307 is offline
#7
Mar29-11, 07:18 PM
P: 27
Okay, so if a divides b, then a = bq, where q is the multiplier, also there is no remainder.

so I see that a = bq and b=aq

solving for q... q^2=1 and q=1

I don't know if I'm onto anything by saying q*q=1, and the lemma are related.
alexk307
alexk307 is offline
#8
Mar29-11, 07:23 PM
P: 27
just got it I think. because q*q = 1, q must equal 1. Therefor a = bq and b = aq can be reduced to a=b and b=a.
gb7nash
gb7nash is offline
#9
Mar29-11, 07:46 PM
HW Helper
P: 805
Quote Quote by alexk307 View Post
so I see that a = bq and b=aq
Not quite. It's true that a = bq, where q is an integer. However, you cannot say b = aq. It could be a different integer, so the simple solution is to make b = ar, where r is an integer.

So now that you have the two equations:

a = bq
b = ar

What can we do?
alexk307
alexk307 is offline
#10
Mar29-11, 07:57 PM
P: 27
oh okay so a=bq and b=ar solving for then rq=1.

So I had the right idea, but I can't say that they're both able to be divided by the same integer, but that rq=1

and then r and q both equal 1, so a=b and b=a.
gb7nash
gb7nash is offline
#11
Mar29-11, 08:05 PM
HW Helper
P: 805
Quote Quote by alexk307 View Post
oh okay so a=bq and b=ar solving for then rq=1.

So I had the right idea, but I can't say that they're both able to be divided by the same integer, but that rq=1

and then r and q both equal 1, so a=b and b=a.
You got it.
alexk307
alexk307 is offline
#12
Mar29-11, 08:25 PM
P: 27
very helpful, thanks for the walkthrough!


Register to reply

Related Discussions
Would anyone be willing to critique my personal statement and statement of purpose? Academic Guidance 1
What is the difference between personal statement and statement of purpose Career Guidance 5
prooving 2 law Classical Physics 4
How do I find the equivalent statement to the statement ~(p -> ~q) Set Theory, Logic, Probability, Statistics 6
Prove the parallelogram law Linear & Abstract Algebra 3