How Can You Prove Number Theory Relationships Using Euclidean Algorithm?

[randommacuser]

1. Prove (a,b)=1 iff (a+b, ab)=1

I'm guessing the main tools I have here are xa+yb=1 and the lemma behind the Euclidean algorithm: if a=bq+r, (a,b)=(b,r). I figure I need to do lots of manipulation to build up a more complicated equality, but I can't make it quite work. Any suggestions?

2. Suppose x an integer such that 0<x<n^3. Show there exist a_0, a_1, a_2 in {0,1,...,n-1} such that x=a_0+a_1n+a_2n^2

I don't even know where to start this one.

 

[StatusX]

For the second one, you mean ...+ a_2 n^2, right? If so, start with the division algorithm x=qn^2+r.

 

[randommacuser]

Yes, that's what I meant; I've changed it now. Thanks for your help!

 

[shmoe]

1) (a+b,ab)=1 => (a,b)=1 can be done the way you have planned, a linear combination of a+b and ab can be turned into a linear combination of a and b. Show what you've tried!

For the other direction, if a prime p divides (a+b,ab) what else can you say it divides?

Did you manage 2)? If not where has StatusX's hint led you?

 

[randommacuser]

Since a,b are assumed to be integers, isn't x(a+b)+yab=(x+yb)a+xb an integer combination? My trouble is the other direction, starting from (a,b)=1. I don't think I see where your question is headed there.

The second problem followed pretty quickly after StatusX's hint.

 

[randommacuser]

All right, I think I follow your question a bit. If a prime divides (a+b,ab) then it divides a+b, ab, and at least one of a or b. What else do I need?

 

[StatusX]

I don't know if this is what shmoe meant, but what about a^2 and b^2?

 

[neurocomp2003]

the 2nd one is simple...its based on the counting principle/grouping and
is about "base numbers" the thing you should think of is how do we create base-number systems ie. binary,tertiary,octal, decimal,hex...how is each one created. what makes a binary number binary and why does the entire binary set contian just the alphabet {0,1}

for the first one is (,) an unknown operator or does it stand for remainder?

 

[randommacuser]

I have the second one now. In the first one, the operator is greatest common divisor.

 

[shmoe]

All right, I think I follow your question a bit. If a prime divides (a+b,ab) then it divides a+b, ab, and at least one of a or b. What else do I need?

You're a small step away, can you show p will divide *both* a and b from what you have?