Question

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?

Answer 1

I only need to prove the backward direction.

Answer 2

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

Answer 3

But how does that prove that m|n?

Answer 4

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

Answer 5

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\)

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

that is one version of euclid lemma

Answer 10

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

Answer 11

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

Answer 12

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?

Answer 13

see *the*

Answer 14

we need to prove this :

If \(a\mid c\) and \(b\mid c\), with \(\gcd(a,b)=1\), then \(ab\mid c\)

Answer 15

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

Answer 16

above is another variant of euclid's lemma

Answer 17

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

Answer 18

Yes, its proof is trivial, try it

Answer 19

what is euclid's lemma according to ur book ?

Answer 20

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

Answer 21

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

Answer 22

oops a|c implies ak = c

Answer 23

multiply c for both sides gives
acx + bcy = c.

and subsitute
a(bs)x + b(ak)y = c

Answer 24

that'll do

Answer 25

ab (sx + ky) = c implies ab|c

whoah I did it!! :D

Answer 26

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

Answer 27

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

Answer 28

oh ... lol

Answer 29

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

Answer 30

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?

Answer 31

i don't get you

Answer 32

what are k1, k2, ... ks ?

Answer 33

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

Answer 34

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)

Answer 35

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

Answer 36

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

Answer 37

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

Answer 38

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.

Answer 39

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

Answer 40

looks good to me, try proving it :)