Let m = p1^e1 * p2^e2 * ... * ps^es, where pi are distinct primes. How does the Fundamental Theorem of Arithmetic proves m|n if and only if pi^ei | n for all i?

- anonymous

- schrodinger

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga.
Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus.
Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your **free** account and access **expert** answers to this

and **thousands** of other questions

- anonymous

I only need to prove the backward direction.

- ganeshie8

Fundamental theorem of arithmetic guarantees you that there are no other prime factorization representations for \(m\)

- anonymous

But how does that prove that m|n?

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- ganeshie8

According to fundamental theorem of arithmetic, the prime factorization representation is unique up to the order of factors.

- ganeshie8

so if each of the prime powers divide \(n\), then by euclid lemma it follows that the product of the prime powers divide \(n\) since \(\gcd({p_i}^{e_i},~{p_j}^{e_j})=1\) for all \(i\ne j\)

- ganeshie8

since fundamental theorem of arithmetic guarantees that there are no other prime factorization representations for \(m\), the proof ends.

- ganeshie8

for example : \(m = 2^35^4\)
suppose \(2^3\mid n\) and \(5^4\mid n\)
since \(\gcd(2^3,5^4)=1\),
by euclid lemma we have \((2^3*5^4)\mid n\)
by fundamental theorem of arithmetic, we know that there are no other prime factorization representations for \(m\), so it follows that \(m\mid n\).

- anonymous

so the Euclid lemma states that if p is a prime, and p | ab, then p|a or p|b correct?

- ganeshie8

that is one version of euclid lemma

- ganeshie8

here is another version
https://i.gyazo.com/9bef4aa867f4a65e0da4c77295d83bdc.png

- ganeshie8

there are couple more variants, but all of them are same.. you can derive one from the other

- anonymous

I'm trying to see that pattern of which letters in Euclid's lemma corresponds to which letters in the question.
So if a|bc, and gcd(a,b) = 1, then a | c
gcd(a,b) is like gcd(p1^e1, p2^e2, ..., ps^es)
right?

- anonymous

see *the*

- ganeshie8

we need to prove this :
If \(a\mid c\) and \(b\mid c\), with \(\gcd(a,b)=1\), then \(ab\mid c\)

- anonymous

right. That's what I just noticed and somehow it doesn't look like Euclid lemma

- ganeshie8

above is another variant of euclid's lemma

- anonymous

O: it's another variation of Euclid's lemma???

- ganeshie8

Yes, its proof is trivial, try it

- ganeshie8

what is euclid's lemma according to ur book ?

- anonymous

Ok. Let me try if you wouldn't mind. Had I known this variation, I wouldn't have asked this question to begin with.
gcd(a,b) = 1 implies there exists x,y such that
ax + by = 1

- anonymous

since a|b and b|c, by definition, ak = b and bs = c

- anonymous

oops a|c implies ak = c

- anonymous

multiply c for both sides gives
acx + bcy = c.
and subsitute
a(bs)x + b(ak)y = c

- ganeshie8

that'll do

- anonymous

ab (sx + ky) = c implies ab|c
whoah I did it!! :D

- anonymous

ok, now I can apply this veriation of Euclid lemma to prove the question
each pi^ei divides n and since gdc(p1^e1, .., ps^es) = 1, by Euclid lemma
m|n

- ganeshie8

sry actually this is not euclid's lemma, this is corollary of bezout's identity

- anonymous

oh ... lol

- anonymous

but anyways, I understood it now. I only need this corollary of bezout's identity to prove. Makes much more sense!

- anonymous

also, I noticed that
m * gcd(k1,k2,...ks) = n
where p1^e1 * k1 = n, ..., ps^es * ks = n.
Do you think it's true?

- ganeshie8

i don't get you

- ganeshie8

what are k1, k2, ... ks ?

- anonymous

by givens, p1^e1 | n, ... ps^es | n . The k1, ...., ks are the integers in the definition of divisibility

- anonymous

I was just trying to prove by definition. I need to find an integer k such that
m k = n.
and what I noticed is k = gcd(k1, k2, ..., ks)

- anonymous

let's use the example above.
2^3 | 10,000
5^4 | 10,000
so,
2^3 * 1250 = 10,000, where k1 = 1250
5^4 * 16 = 10,000, where k2 = 16
gcd(1250,16) = 2
and coincidentally, 2^3 * 4^2 * 2 = 10,000

- anonymous

I think this only works if gcd(2^3, 5^4) = 1, which it is

- anonymous

typo :O 2^3 * 5^4 * 2 = 10,000

- anonymous

so here is the conjecture.
If a | n and b|n and gcd(a,b) = 1, then ab * gcd(x,y) = n, where ax = n and by = n.
If you have any comments to this conjecture, let me know. What matters is that I understood how to prove the original question.

- anonymous

btw @ganeshie8 Thank you for helping me with the original question :)

- ganeshie8

looks good to me, try proving it :)

Looking for something else?

Not the answer you are looking for? Search for more explanations.