anonymous
  • anonymous
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?
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
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.
schrodinger
  • schrodinger
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
anonymous
  • anonymous
I only need to prove the backward direction.
ganeshie8
  • ganeshie8
Fundamental theorem of arithmetic guarantees you that there are no other prime factorization representations for \(m\)
anonymous
  • 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
  • ganeshie8
According to fundamental theorem of arithmetic, the prime factorization representation is unique up to the order of factors.
ganeshie8
  • 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
  • ganeshie8
since fundamental theorem of arithmetic guarantees that there are no other prime factorization representations for \(m\), the proof ends.
ganeshie8
  • 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
  • anonymous
so the Euclid lemma states that if p is a prime, and p | ab, then p|a or p|b correct?
ganeshie8
  • ganeshie8
that is one version of euclid lemma
ganeshie8
  • ganeshie8
here is another version https://i.gyazo.com/9bef4aa867f4a65e0da4c77295d83bdc.png
ganeshie8
  • ganeshie8
there are couple more variants, but all of them are same.. you can derive one from the other
anonymous
  • 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
  • anonymous
see *the*
ganeshie8
  • ganeshie8
we need to prove this : If \(a\mid c\) and \(b\mid c\), with \(\gcd(a,b)=1\), then \(ab\mid c\)
anonymous
  • anonymous
right. That's what I just noticed and somehow it doesn't look like Euclid lemma
ganeshie8
  • ganeshie8
above is another variant of euclid's lemma
anonymous
  • anonymous
O: it's another variation of Euclid's lemma???
ganeshie8
  • ganeshie8
Yes, its proof is trivial, try it
ganeshie8
  • ganeshie8
what is euclid's lemma according to ur book ?
anonymous
  • 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
  • anonymous
since a|b and b|c, by definition, ak = b and bs = c
anonymous
  • anonymous
oops a|c implies ak = c
anonymous
  • anonymous
multiply c for both sides gives acx + bcy = c. and subsitute a(bs)x + b(ak)y = c
ganeshie8
  • ganeshie8
that'll do
anonymous
  • anonymous
ab (sx + ky) = c implies ab|c whoah I did it!! :D
anonymous
  • 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
  • ganeshie8
sry actually this is not euclid's lemma, this is corollary of bezout's identity
anonymous
  • anonymous
oh ... lol
anonymous
  • anonymous
but anyways, I understood it now. I only need this corollary of bezout's identity to prove. Makes much more sense!
anonymous
  • 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
  • ganeshie8
i don't get you
ganeshie8
  • ganeshie8
what are k1, k2, ... ks ?
anonymous
  • anonymous
by givens, p1^e1 | n, ... ps^es | n . The k1, ...., ks are the integers in the definition of divisibility
anonymous
  • 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
  • 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
  • anonymous
I think this only works if gcd(2^3, 5^4) = 1, which it is
anonymous
  • anonymous
typo :O 2^3 * 5^4 * 2 = 10,000
anonymous
  • 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
  • anonymous
btw @ganeshie8 Thank you for helping me with the original question :)
ganeshie8
  • ganeshie8
looks good to me, try proving it :)

Looking for something else?

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