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

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- schrodinger

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

- 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.