simple mod arithmetic question (1 Viewer)

[underthesun]

given x | y^m, y | xⁿ, y | z^o, z | y^p, for any integer m,n,o,p, are you able to deduce that x | z^q and z | x^r for any integer q and r?

This is from discrete maths, I was trying to prove transitivity. Just doesn't know how to do it :S

 

[wogboy]

Remember the definition of a | b, which means there exists an integer n such that:
b = an.

Transitivity proof for 3 variables:
"if a|b & b|c, then a|c."

a|b iff b = am for some integer m,
b|c iff c = bn for some integer n,
so c = amn = (mn)a

since mn is an integer (integers are closed under multiplication), then
a | c

This can also be generalised to cases with many variables using induction:
e.g. if b_0|b_1 & b_1|b_2 & b_2 | b_3 & ...& b_n-1 | b_n, then b_0 | b_n

given x | y^m, y | x^n, y | z^o, z | y^p, for any integer m,n,o,p, are you able to deduce that x | zq and z | xr for any integer q and r?

x | y^m, y | x^n, y | z^o, z | y^p, for any integer m,n,o,p
iff x|y and y|x and y|z and z|y.
iff x=y=z

since x = z,
x | z,
so by transitivity x | z^q (for all integers q)
also z | x,
so by transitivity again, z | x^r.

 

[Affinity]

^^ let me compress this:

let m,n,o,p = 1
x|y implies abs(x) <= abs(y)
y|x implies abs(y) <= abs(x)

therefore y = +/- x
similarly z= +/- y
therefore z= +/- x
so x | z^q, z| x^r for any q,r

 

[underthesun]

actually Im very sorry, but I misstated the question

It was actually "for some positive integers m and n", so not m, n, o, p.

Ill just write the original:

Let Z⁺ be the set of positive integers. Define a releation on Z⁺ by x ~ y if and only if x | y^m and y | xⁿ for some positive integers m and n.

a) Show that ~ is an equivalence relation on Z⁺
b) Are the numbers 100 and 99 in the same equivalence class? Explain.
c) Describe the equivalence class containing 30.
d) Which equivalence class contains only one element?

sorry guys

edit: Im reading your solutions now, this is just because I read affinity's short one first (it looks simpler ), and he assumed that you can let m, n, o, p = 0. Really sorry for this T_T

edit: headache. ill just read your solution tomrorow wogboy.. but thanks guys :doughnut:

 

[Affinity]

oops.. I was meant to write m,n,o,p = 1 in teh original.

hmm anyway.. for the actual question.

the equivalence relation is "having the same prime factors(not neccessarily to the same power)". Prove the if part and the only if part separately.

a).. trivial.. it's symmetric, it's reflexive and it's transitive.
b.) Well no... 99 does not divide 100^n for any n because 100 does not have 3 as a factor and 99 does.

c.) 30 = 2*3*5, so the equivalence class containing 30 will be
{2^p * 3^q * 5^r : , p,q,r >= 1}

d.) {1}