Number Theory fundamental theorem of arithemetic

[trap101]

I have two full questions on some number theory questions I've been working on, I guess my best bet would be to post them separately.

1) Suppose that n is in N (natural numbers), p₁,...,p_n are distinct primes, and l₁,...l_n are nonnegative integers. Let m = p₁^l₁p₂^l₂...p_n^l_n. Let d be in N such that d ≥ 2 and d divides m.

a) Using the fundamental theorem of arithemetic prove that p is a prime that divides d, then p_i for some i in {1,...,n}.

Attempt: Since d is in N and d ≥ 2, this means that d itself is a product of primes (prime factorization) or a prime itself. This means d = p₁p₂...p_n (product of primes). Then there exists a p that divides d. (Since we are starting from 1 in the natural numbers)

Is this the right idea and what would be a clearer way of writing this as a proof?

b) Suppose the i is in {1,...,n}. Prove that p_i^k does not divide d if
k > l_i

Attempt: if k > l_i then d ≠ p_i^k, but d may equal any prime in m = p₁^l₁p₂^l₂...p_n^l_n since we know d | m.

this would imply d has a cononical factorization : p₁^l₁p₂^l₂...p_n^l_n and we know k > l_i therefore p_i^k does not divide d.

Right idea?

 

[Deveno]

"n" is sort of irrelevant to the proof, it just serves to underscore that m is a product of a finite number of prime powers.

the important fact is that d|m.

we suppose that p is a prime dividing d, and we want to prove that p is one of the prime factors listed in the given factorization of m.

the fundamental theorem of arithmetic tells us the given factorization is unique.

(well, it is if we list the primes p_i in ascending order p₁<...< p_n).

the first step should be to prove that p|m.

the next step should involve this fundamental fact about primes:

if p is a prime, and p|ab, then either p|a, or p|b (or perhaps both).

under what circumstances will p|p_i^l_i ?

for part (b): suppose, by way of contradiction, that k > l_i, but that somehow p_i^k divided d.

wouldn't pⁱ_k also divide m? re-write:

m/(p_i^k) in some form that leads to a contradiction (you may assume l_i = k+r, for some r > 0).

*****

to bring this "back to earth", let's see an example:

suppose m = 72 = 8*9 = (2³)(3²).

if d is any divisor of 72, can there be any prime factors of d besides 2 and 3? could any multiple of 5 be a divisor of 72? how about 7? what do you think?

 

[trap101]

the first step should be to prove that p|m.

the next step should involve this fundamental fact about primes:

if p is a prime, and p|ab, then either p|a, or p|b (or perhaps both).

under what circumstances will p|p_i^l_i ?

To work on the first portion of this, the only way I could come up with being able to show that p|m is by the fact that I'm told that d|m, since this is the case, d can be written as a product of primes (call them the series of q's). Since we know d | m, this means (series of q's)|m. From the fact of primes that if p is a prime and p | ab, then p|a or p|b, we can say since d|m => (series of q's)|m => (a q of series of q's)|p₁ or (a q of series of q's)|p₂ or ...(a q of series of q's)|p_n

under what circumstances will p|p_i^l_i ?

I haven't been able to figure it out. Now thinking about it, I don't even think I proved that p|d...smh.

 

[Deveno]

theorem:

if a|b and b|c, then a|c

proof:

suppose a|b and b|c. then b = ka, for some integer k, and c = mb, for some integer m.

hence: c = mb = m(ka) = (mk)a, so a|c, since mk is surely an integer.

*****

i think what is giving you trouble is you want to "factorize" d. well, you COULD...and you'd have a list of d as some product like:

d = q₁^k₁q₂^k₂...q_r^k_r,

and then you'd have to show that each q equalled "some" p, and that each power was less than or equal to the corresponding power in the factorization of m. this is actually doable, but keeping track of the exponents and subscripts is tedious, and in the end, not very instructive.

if p|d, and d|m...by the above theorem, p|m. think about this: we have a factorization of m into powers of primes, which we know is unique, and we have that p is a prime dividing m. how can p NOT be one of those primes in the factorization of m?

if i asked you: which primes divide 32760, would you consider that "a hard problem?". is it possible that 11 divides 32760? what about 17, or 163? how would you even begin to start answering those problems?

well, what if i told you that:

32760 = (2³)(3²)(5)(7)(13)

is it any clearer which primes divide 32760?

******

for your second question...does 3 divide 16? 32? 64? does 3 divide ANY power of 2? does 3 divide any power of 7? does 3 divide any power of any other prime? can you generalize this to prime numbers besides 3?