Find the sum of the positive divisors of x

[GodlessAstronomer]

Can someone tell me how to find the sum of the positive divisors of a number? For example, the number 1200 has prime factorization 2^4 x 3 x 5^2, so it has 5x2x3=30 positive divisors (correct?), but how do I find the sum of the divisors?

Bonus question
I know Euclid's algorithm like the back of my hand, but how do I apply it to gigantic numbers in a reasonable amount of time? I need to show that (6x301^10 + 7) and (3x301^10 + 2) are co-prime using Euclid's algo, I'm not quite sure how to approach this problem.

Just so you guys know I'm not asking for you to do my homework, I'm studying for an exam and the previous years' exams don't have solutions posted 🙂

 

[bobsmith1492]

I could do some quick C code; the modulus operator makes it easy ... or do you want a mathematical answer??

 

[GodlessAstronomer]

Originally posted by: bobsmith1492
I could do some quick C code; the modulus operator makes it easy ... or do you want a mathematical answer??

I'm studying for a discrete maths exam so I need a mathematical answer, thanks anyway.

 

[Jeff7]

Use a spreadsheet. 😛

 

[TuxDave]

Originally posted by: GodlessAstronomer
Can someone tell me how to find the sum of the positive divisors of a number? For example, the number 1200 has prime factorization 2^4 x 3 x 2^5, so it has 5x2x6=60 positive divisors (correct?), but how do I find the sum of the divisors?

Bonus question
I know Euclid's algorithm like the back of my hand, but how do I apply it to gigantic numbers in a reasonable amount of time? I need to show that (6x301^10 + 7) and (3x301^10 + 2) are co-prime using Euclid's algo, I'm not quite sure how to approach this problem.

Just so you guys know I'm not asking for you to do my homework, I'm studying for an exam and the previous years' exams don't have solutions posted 🙂

wat

 

[GodlessAstronomer]

Originally posted by: TuxDave
For example, the number 1200 has prime factorization 2^4 x 3 x 2^5, so it has 5x2x6=60 positive divisors (correct?), but how do I find the sum of the divisors?
)

wat[/quote]

Oops that should say 5^2 not 2^5, fixed that. Just an example I pulled out of my ass.

 

[El Guaraguao]

ok godlessasstronomer, we get it. your intellect is vastly superior than your average atoter. gee willikers!

oh btw the answer to your question is that you find the root of eleventy and multiply with a random number.

 

[TuxDave]

Originally posted by: GodlessAstronomer
Can someone tell me how to find the sum of the positive divisors of a number? For example, the number 1200 has prime factorization 2^4 x 3 x 5^2, so it has 5x2x3=30 positive divisors (correct?), but how do I find the sum of the divisors?

Bonus question
I know Euclid's algorithm like the back of my hand, but how do I apply it to gigantic numbers in a reasonable amount of time? I need to show that (6x301^10 + 7) and (3x301^10 + 2) are co-prime using Euclid's algo, I'm not quite sure how to approach this problem.

Just so you guys know I'm not asking for you to do my homework, I'm studying for an exam and the previous years' exams don't have solutions posted 🙂

Ok so to answer your question, imagine a number with prime factorization A^X * B^Y * C^Z.

The sum of the divisors will look like:
A^0*B^0*C^0 + A^0*B^0*C^1 + A^0*B^0*C^2... +
A^0*B^1*C^0 + A^0*B^1*C^1 + A^0*B^1*C^2 ... +
A^0*B^2*C^0 + A^0*B^2*C^1 + A^0*B^2*C^3 ... +
...
A^1*B^0*C^0 + A^1*B^0*C^1 + A^1*B^0*C^0 ...+ and so on.

Factor the first line by A^0*B^0, 2nd line by A^0*B^1... etc and you get

A^0*B^0*(C^0+C^1+C^2...+C^Z) +
A^0*B^1*(C^0+C^1+C^2...+C^Z) +
..
A^1*B^0*(C^0+C^1+C^2...+C^Z) +
A^1*B^1*(C^0+C^1+C^2...+C^Z) +
...

Factor the next group by A^0*(C^0+C^1+C^2...+C^Z) and the next group by A^1*(C^0+C^1+C^2...+C^Z) etc..

A^0*(C^0+C^1+C^2...+C^Z)*(B^0 + B^1 + ... B^Y)+
A^1*(C^0+C^1+C^2...+C^Z)*(B^0 + B^1 + ... B^Y)+
A^2*(C^0+C^1+C^2...+C^Z)*(B^0 + B^1 + ... B^Y)+

And then factor out by (C^0+C^1+C^2...+C^Z)*(B^0 + B^1 + ... B^Y) and you get

(A^0 + A^1... A^X)(B^0+B^1+...B^Y)(C^0 + C^1 ... C^Z)

So then we can get the generalized form for any factorization.

 

[TheVrolok]

Originally posted by: mofoe2001
ok godlessasstronomer, we get it. your intellect is vastly superior than your average atoter. gee willikers!

oh btw the answer to your question is that you find the root of eleventy and multiply with a random number.

I also can't decide if these are thinly veiled brag threads, or if he holds the honest hope that there are enough true nerds here at AT that he might get some help. His last homework question got a legit response, so I still can't decide.

 

[GodlessAstronomer]

Originally posted by: mofoe2001
ok godlessasstronomer, we get it. your intellect is vastly superior than your average atoter. gee willikers!

oh btw the answer to your question is that you find the root of eleventy and multiply with a random number.

This is elementary discrete maths, there are a ton of EE and CompSci students on this board who would have done this stuff, I'm just asking for help.

TuxDave, thanks for your help mate.

 

[Kirby]

I've done discrete before, but I have no guarantee that I can do it, much less do it correctly. 😛

 

[ebaycj]

Originally posted by: GodlessAstronomer

Originally posted by: bobsmith1492
I could do some quick C code; the modulus operator makes it easy ... or do you want a mathematical answer??

I'm studying for a discrete maths exam so I need a mathematical answer, thanks anyway.

Discrete Math. Singular.