Asked by lost
How do you prime factorize the numbers 8678670 and 15485863?
Answers
Answered by
oobleck
clearly, 10 (and thus 2 and 5) divide 8678670
8678670 = 2*5*867867
Now it is clear that
867867 = 867 * 1001
Since the digits of 867 sum to 21, it is divisible by 3
867 = 3*289
Now you just start testing primes, up to √289 = 17
Aha! now we are done with 867 = 17^2
As for 1001, start testing primes, up to √1001 ≈ 31
3,5,7 clearly do not divide 1001
11*91 = 1001
91 = 7*13
So 1001 =11*7*13
And so we know that
8678670 = (2*5)(3*17^2)(7*11*13) = 2•3•5•7•11•13•17^2
Do any others in the same way. Use casting out 3's and casting out 9's, repeated groups, and prime testing up to √N. Why stop there? Because if one factor is greater than √N, the other will be less than √N, so you will have already found it.
8678670 = 2*5*867867
Now it is clear that
867867 = 867 * 1001
Since the digits of 867 sum to 21, it is divisible by 3
867 = 3*289
Now you just start testing primes, up to √289 = 17
Aha! now we are done with 867 = 17^2
As for 1001, start testing primes, up to √1001 ≈ 31
3,5,7 clearly do not divide 1001
11*91 = 1001
91 = 7*13
So 1001 =11*7*13
And so we know that
8678670 = (2*5)(3*17^2)(7*11*13) = 2•3•5•7•11•13•17^2
Do any others in the same way. Use casting out 3's and casting out 9's, repeated groups, and prime testing up to √N. Why stop there? Because if one factor is greater than √N, the other will be less than √N, so you will have already found it.
There are no AI answers yet. The ability to request AI answers is coming soon!
Submit Your Answer
We prioritize human answers over AI answers.
If you are human, and you can answer this question, please submit your answer.