1. ## Prime Factorization

What is the prime factorization of 770?

770 = 70 * 11

70 = 35 * 2

35 = 7 * 5

So, the answer is 2 * 5 * 7 * 11.

2 * 5 * 7 * 11 = 770

2. ## Re: Prime Factorization

Originally Posted by harpazo
What is the prime factorization of 770?

770 = 70 * 11

70 = 35 * 2

35 = 7 * 5

So, the answer is 2 * 5 * 7 * 11.

2 * 5 * 7 * 11 = 770
Suppose we want to factor any number. Say 26700456. That is random, but here it is
The point being that today the web provides students with resources that could only be imagined even twenty years ago.

But if you want to understand look at this.
$1000000000000000$ that is a one with fifteen zeros. That is $10^{15}$
Now $10=2\cdot 5$ So that $10^{15}=[2\cdot 5]^{15}=2^{15}\cdot 5^{15}$
Thus now you have a prime factorization of a very large number. Done without any help of technology.
Done because you understand the process.
What is the prime factorization of $17,621,968,000,000,000~?$

3. ## Re: Prime Factorization

Originally Posted by harpazo
What is the prime factorization of 770?

770 = 70 * 11

70 = 35 * 2

35 = 7 * 5

So, the answer is 2 * 5 * 7 * 11.

2 * 5 * 7 * 11 = 770

There are simple tests for divisibility by small numbers, such as if the rightmost digit is divisible by 2, then then entire number is also. If the sum of the digits is divisible by 3, then the number is also. If the rightmost two digits is divisible by 4, then the number is also. If the rightmost digit is divisible by 5, then so is the number. If the number passes the tests of divisibility for 2 and 3, then it is divisible by 6. I would look up tests for divisibility and become at least familiar with them.

4. ## Re: Prime Factorization

Thank you everyone.

5. ## Re: Prime Factorization

Originally Posted by Plato
Suppose we want to factor any number. Say 26700456. That is random, but here it is
The point being that today the web provides students with resources that could only be imagined even twenty years ago.

But if you want to understand look at this.
$1000000000000000$ that is a one with fifteen zeros. That is $10^{15}$
Now $10=2\cdot 5$ So that $10^{15}=[2\cdot 5]^{15}=2^{15}\cdot 5^{15}$
Thus now you have a prime factorization of a very large number. Done without any help of technology.
Done because you understand the process.
What is the prime factorization of $17,621,968,000,000,000~?$
How do we start this one?

6. ## Re: Prime Factorization

Originally Posted by harpazo
How do we start this one?
The same approach as I think we all use (unless you are using some kind of more advanced algorithms.)

How many times can you divide 17621968000000000 by 2? How many times can you divide what's left by 3? Etc.

-Dan

7. ## Re: Prime Factorization

To factor the number Plato gave, 17,621,968,000,000,000, I would first note that it is (17,621,968)(1,000,000,000). 1,000,000,000= 10^9= (2^9)(5^9).

Now the hard part! 17,621,968 is even: 17,621,968= 2(8,810,984)= 2(2)(2)(4,405,492)= 2(2)(2)(2)(2,202,746)= 2(2)(2)(2)(2)(1101373). That last number is not even. Further, since its digit sum, 1+ 1+ 0+ 1+ 3+ 7+ 3= 16, is not divisible by 3, 3 is not a factor or 1101373. The last digit is not a "0" or a "5" so it is not divisible by 5. There is a test for divisibility by 7: subtract twice the last digit from the number. The original number is divisible by 7 if and only if the new one is. Here 1101373- 6= 1101367. If it is not obvious that that is divisible by 7, do it again- or just go ahead and try dividing by 7! 1101373/7= 157339 so 17,621,968= (2^5)(7)(157339). But 157339= 7(22477)= 7(7)(3211) while 3211 is not divisible by 7. The next larger prime number is 11 but 3211 is not divisible by 11. 3211= 13(247)= 13(13)(19). 19 itself is prime so we have 17,621,968= (2^5)(7^2)(13^2)(19).

So we have 17,621,968,000,000,000= [(2^9)(5^9)][(2^5)(7^2)(13^2)(19)]= (2^14)(5^9)(7^2)(13^2)(19)

8. ## Re: Prime Factorization

try factoring $19249 \times 2^{13018586} + 1$

(hint: it's easier than it looks!)

9. ## Re: Prime Factorization

Originally Posted by HallsofIvy
To factor the number Plato gave, 17,621,968,000,000,000, I would first note that it is (17,621,968)(1,000,000,000). 1,000,000,000= 10^9= (2^9)(5^9).

Now the hard part! 17,621,968 is even: 17,621,968= 2(8,810,984)= 2(2)(2)(4,405,492)= 2(2)(2)(2)(2,202,746)= 2(2)(2)(2)(2)(1101373). That last number is not even. Further, since its digit sum, 1+ 1+ 0+ 1+ 3+ 7+ 3= 16, is not divisible by 3, 3 is not a factor or 1101373. The last digit is not a "0" or a "5" so it is not divisible by 5. There is a test for divisibility by 7: subtract twice the last digit from the number. The original number is divisible by 7 if and only if the new one is. Here 1101373- 6= 1101367. If it is not obvious that that is divisible by 7, do it again- or just go ahead and try dividing by 7! 1101373/7= 157339 so 17,621,968= (2^5)(7)(157339). But 157339= 7(22477)= 7(7)(3211) while 3211 is not divisible by 7. The next larger prime number is 11 but 3211 is not divisible by 11. 3211= 13(247)= 13(13)(19). 19 itself is prime so we have 17,621,968= (2^5)(7^2)(13^2)(19).

So we have 17,621,968,000,000,000= [(2^9)(5^9)][(2^5)(7^2)(13^2)(19)]= (2^14)(5^9)(7^2)(13^2)(19)

10. ## Re: Prime Factorization

Originally Posted by romsek
try factoring $19249 \times 2^{13018586} + 1$

(hint: it's easier than it looks!)
Uh huh. Whatever you say.

-Dan

11. ## Re: Prime Factorization

Originally Posted by romsek
try factoring $19249 \times 2^{13018586} + 1$

(hint: it's easier than it looks!)
Originally Posted by topsquark
Uh huh. Whatever you say.

-Dan
The factors are $19249 \times 2^{13018586} + 1$ and $1$

12. ## Re: Prime Factorization

Originally Posted by romsek
The factors are $19249 \times 2^{13018586} + 1$ and $1$
Okay, I'll bite. How did you know that $\displaystyle 19249 \times 2^{13018586} + 1$ is prime? I don't have that many fingers!

-Dan

13. ## Re: Prime Factorization

Originally Posted by topsquark
Okay, I'll bite. How did you know that $\displaystyle 19249 \times 2^{13018586} + 1$ is prime? I don't have that many fingers!

-Dan
see https://en.wikipedia.org/wiki/Larges...n_prime_number

Currently it ranks as the 20th largest known prime.

14. ## Re: Prime Factorization

Interesting good notes.