TT's Maths Thread

[kamil9876]

let's prove 2 first.

suppose c|a and c|b.

ax+by=(a,b) for some x,y.

a=a'c, b=b'c for some b',a'.

(a,b)=c(a'x+b'y) hence c divides (a,b)

Now to prove the converse:

for some

Since c|(a,b), (a,b)=cc' for some c':

Hence a=cc'a'=c(cc'a')

thus a is a multiple of c.

To prove b is a multiple of c, just repeat the same argument with b in place of a.

[kamil9876]

let's prove 1 now:

for LHS, we seek the greatest number that divides all numbers in the set

for RHS, we seek the greatest number that divides

But from 2 we know that the greatest number that divides both elements in is also the greatest number that divides .

[TrueTears]

let's prove 2 first.

suppose c|a and c|b.

ax+by=(a,b) for some x,y.

a=a'c, b=b'c for some b',a'.

(a,b)=c(a'x+b'y) hence c divides (a,b)

Now to prove the converse:

for some

Since c|(a,b), (a,b)=cc' for some c':

Hence a=cc'a'=c(cc'a')

thus a is a multiple of c.

To prove b is a multiple of c, just repeat the same argument with b in place of a.

3rd last line, is that a typo? should be c(c'a')?

let's prove 1 now:

for LHS, we seek the greatest number that divides all numbers in the set

for RHS, we seek the greatest number that divides

But from 2 we know that the greatest number that divides both elements in is also the greatest number that divides .

Thanks for that, I'm happy with your explanation but how would you include Euclid's algorithm in it?

[kamil9876]

3rd last line, is that a typo? should be c(c'a')?

yes

Thanks for that, I'm happy with your explanation but how would you include Euclid's algorithm in it?

this proof provides a method for finding the gcd of more than two numbers. For example.


and so we can use our technique for finding gcd of two numbers and then do this simplification, and then use it again for the RHS (since we have two numbers now).

If we had n numbers, just keep using this repetetively and notice how the ammount of numbers in gcd(...) decreases by one in each step, until eventually you will ahve only two numbers there.

[TrueTears]

Oh thanks kamil, so Euclid's algorithm is just simply repeated uses of another algorithm? In the case before to find the GCD it is the repeated use of the division algorithm, while here it is the repeated use of finding the GCD?

[kamil9876]

yeah

[TrueTears]

Just started on some Linear Diophantine equations

Let and be integers, with and not both , and let . Then the equation  has an integer solution if and only if is a multiple of , in which case there are infinitely many solutions. These are the pairs , where n and is any particular solution.

How do you prove that , are the general solutions?

Thanks

[kamil9876]

There is a graphical motivation fo the following proof:




now any other solution can be written in the form (ie: our "run" and "rise" respectively).






Thus we are after all common multiples of and . The lowest common multiple of a and b is and all common multiples of and are multiples of of the lcm: (prove this as an exercise)

Thus



and now do a similair job to find .

[TrueTears]

There is a graphical motivation fo the following proof:




now any other solution can be written in the form (ie: our "run" and "rise" respectively).






Thus we are after all common multiples of and . The lowest common multiple of a and b is and all common multiples of and are multiples of of the lcm: (prove this as an exercise)

Thus



and now do a similair job to find .

Wait how can since if we change and then ain't we changing to some other multiple of ?

As in the numerical value of for is different to that of

So why can you equate them?

[kamil9876]

now any other solution can be written in the form x=x_0+h, y=y_0+g  (ie: our "run" and "rise" respectively).

a straight forward consequence of "another solution"[to the SAME equation]

[TrueTears]

now any other solution can be written in the form x=x_0+h, y=y_0+g  (ie: our "run" and "rise" respectively).

a straight forward consequence of "another solution"[to the SAME equation]

Ahhh yeah, thanks I get the proof now


A good question:

If and are integers when does the Diophantine equation have integer solutions ?

[zzdfa]

Let g=gcd(a1,...,an)
g divides a1 ... an, thus it divides any integer linear combo of a1,...,an.
applying the same logic you use to prove that ax+by=c  has integer solution iff gcd(a1,...,an)|c:
the equation has a solution iff c is a multiple of gcd(a1,...,an).

[TrueTears]

Ahhh yeah, thanks zzdfa

[TrueTears]

Eisenstein's criterion states that if where , if is a prime and but not and it does not divide , then is irreducible.

I've actually used this criterion several times in the past while doing algebra problem solving questions, but I've never bothered to try to prove it, now that I'm doing number theory, how would you prove it?

[kamil9876]

suppose it is redducible, then:



is not divisible by , hence and are both not divisible by . is divisible by , but not by , thus one of these terms is not divisible by , say WLOG .



but is divisibly by , is (since is). must therefore be divisible by , but since isn't then must be.

hence so far we now know that and are divisible by .



now we use a similair argument to show that b_2 is divisible by p. Hence we keep doing this until we get b_q is divisibly by p, which contradicts what we know. Eventually this proof is tantamount to the technique used in this old problem we solved earlier (problem 1)