Thread: smallest element

Let u,v ∈ \ {0} define A as A={a∈ N\{0} : u|a and v|a}

I want to prove two things
1) I want to show that A has a smallest element and call this b
2) Show that for every a∈ A follows b|a

1) I know that a fundamental follow of the axiom of induction is that every not empty subset of N contains a smallest element.
I need to show that A is a not empty subset. ( I don't know how to do this because I have no questions or explanation in my math book )

1) I need to show that A is a not empty set
there exist an a so that a=|u*v| so A is not empty so A has a smallest element b

Did I tell it correct ?

Originally Posted by Burcin

1) I need to show that A is a not empty set
there exist an a so that a=|u*v| so A is not empty so A has a smallest element b

Did I tell it correct ?

Yes. To be more precise, the claim is not that |u * v| exists, but that it is in A. And to be very detailed, you could explain why |u * v| is in A, i.e., why it does not equal 0 and is divisible by u and v.

To prove 2), consider the remainder r when some arbitrary a is divided by b. Note that 0 <= r < b by the definition of remainder (at least when a >= 0). Show that r is divisible by u and v.

1) I need to prove that A is not empty
prove: a=|v*u| and u ≠ 0 and v ≠ 0 so for very a∈ A there is a number dividable for u and v, so the set A isn't empty and has a smallest element

2) a=q*b +r so r=a-(q*b) r∈A because q*b∈A and a∈A
this isn't right because r<b and b is not the smallest element

So we have a contradiction because we said in 1) that b was the smallest element

Originally Posted by Burcin

1) I need to prove that A is not empty
prove: a=|v*u| and u ≠ 0 and v ≠ 0 so for very a∈ A there is a number dividable for u and v, so the set A isn't empty and has a smallest element

No. To prove that a set {y ∈ Y : P(y)} is not empty you need to exhibit an element x of the set. Further, to prove that x ∈ {y ∈ Y : P(y)}, you need to show that x ∈ Y and P(x). You constructed a potential element a = |v * u|, but you have not shown that a ∈ {a ∈ N \ {0} : u | a and v | a} because you have not shown, or even claimed, that a ∈ N \ {0} or that u | a and v | a. In showing this, you need to talk about this concrete a = |v * u| and not about every a ∈ A.

Originally Posted by Burcin

2) a=q*b +r so r=a-(q*b) r∈A because q*b∈A and a∈A
this isn't right because r<b and b is not the smallest element

This is the right direction, but your reasoning omits more details than is appropriate for a claim of this complexity. You need to explain why q * b ∈ A and why the difference of two elements of A is again in A.

2) a=q*b+r 0<=r<|b| if r=0 then q=a/b you can also right b|a

Prove; if a is not divisible by b then
r=a-(q*b)
r∈A because a∈A and q*b∈A so r<b Contradiction!
We stated that b was the smallest element of the set A not r So r=0 so q=a/b
So for every a∈ A is divisible by b

Oke I am going to have a look at it

Originally Posted by Burcin

Let u,v ∈ \ {0} define A as A={a∈ N\{0} : u|a and v|a}
I want to prove two things
1) I want to show that A has a smallest element and call this b
2) Show that for every a∈ A follows b|a

Here are some different considerations.
Let . Is

If is there a contradiction there?

If then where .