What are all the prime factors of (20 to the 30th power) minus one?

Question

20 ^30-1?
(It ends up being 1,073,741,823 as a whole number)

Please help!

Answer 1

You meant 2^30 - 1 = 1,073,741,823

The prime factors are:

3(twice), 7, 11, 31,151 and 331

That is: 1,073,741,823 = 3^2 x7x11x31x151x331

Here's a good factoring link:

http://www.farfarfar.com/math/calculators/factoring/

Note: there are some simple theorems that can facilitate factoring:

For example: 2^30 -1 = (2^15 -1)(2^15 +1)

2^15 + 1 = (2^3)^5 + 1 = (2^5)^3 +1. From Fermat's little theorem this tells us that 2^3 + 1= 9 and 2^5 +1 = 33 = 3x11 are factors.
Similarly, 2^15 -1 = (2^3)^5 - 1 = (2^5)^3 -1 tells us 2^3 -1 =7 and 2^5 -1 = 31 are factors. If we divide 1073741823 by 3^2 x 7 x11x31 we get 49981 = 151 x331 and 151 and 331 are both prime.

Answer 2

I disagree with the previous poster's opinion that 20^30 - 1 is prime. In fact, one could factor it as follows:

(20^30 - 1) = (20^15 - 1)(20^15 + 1)
= [ (20^5 - 1)(20^10 + 20^5 + 1) ] [ (20^5 + 1)(20^10 - 20^5 + 1) ]
= [ (20 - 1)(20^4 + 20^3 + 20^2 + 20 + 1)(20^10 + 20^5 + 1) ] [ (20 + 1)(20^4 - 20^3 +20^2 -20 + 1)(20^10 - 20^5 + 1) ]

Hence, I could partially answer your question by saying that 19 = 20 - 1, 3 and 7 (i.e. 3*7 = 21 = 20 + 1) are some of the prime factors of 20^30 - 1. In general, it is NOT a simple matter to determine prime factors of numerical expressions of the form a^n - 1, where a and n are positive integers. You could try looking up cyclotomic polynomials, for instance, if you'd like further information regarding this matter.

Answer 3

If you add the digits, you'll find that the sum is 36, which is a multiple of 3, and in fact a multiple of 9. And you probably know that this makes the number divisible by 3 (and by 9), so it's not a prime. (Note: This add-the-digits approach works for 3 and 9, but not for any other number (in base 10).)

Anyway, start by dividing by 3. Take the quotient and divide by 3 again. (You now have 3 as a prime factor TWO TIMES.) Try dividing by 3 again. If that doesn't work, divide by the next prime: 5. OK, forget about 5 because the number is obviously not a multiple of 5.

So divide by 7 and see whether that works. See how many times you can divide by 7, then 11, then 13, etc. Keep track of the prime factors that you have successfully divided by.

Hint: The largest prime factor is 331, and there are 7 factors (keeping in mind that 3 counts twice).

Well, darn it. Jimbo gave away the answer, except that he failed to mention that 3 is a factor twice, so his answer isn't quite right.

Answer 4

You asked 20^30 -1
but 1,073,741,823 is 2^30 -1 (not 20)

The factors of 1,073,741,823 are 3*3*7*11*31*151*331


(((EDIT))) 2 hours after my original answer


20^30 = (2*10)^30 = 2^30 *10^30=
1073741824
000000000000000000000000000000

subtract 1 from that to get
1073741823
999999999999999999999999999999

I used Big Number Cruncher 1.05 to factor this to get it's prime factors

3*3*7*11*19*31*61*127*251*421*
3001*152381*261451*26876632021

Answer 5

That sounds like one of those known large primes.