# Divisibility

• Feb 26th 2010, 06:39 PM
smahanta
Divisibility
The question goes like this:
(x^n -1) is divisible by (x-1) when "n" is a natuaral number.According to this rule state whether (2^60 -1) is divisible by 11, 13, 17, 19,23.

My own solution:
Factors of 60 = (2,30), (3,20), (4,15), (5,12), (6,10), (10,6),(12,5)
So 2^60 -1 = {(2^2)^30} -1. Assuming x = 2^2 ie 4 => 4^30 -1 => 3|(2^60-1)
By same reasoning x could be 8, 16, 32, 64, 1024, 4096.
So some of the divisors of 2 ^60 -1 are 7,15,31,63,1023,4095.
As it is divisible by 15, so it is divisible by 5 as well.
As it is divisible by 63, so it is divisible by 21 as well.
As it is divisible by 1023, so it is divisible by 11 & 93 as well.
As it is divisible by 4095, so it is divisible by 13 as well.
So as per me it is divisible by 11, 13 but not by 17, 19 & 23. I have verified this using calculator.
Is this the correct way to go for this kind of problem?
• Feb 27th 2010, 08:37 AM
qmech
I agree with your conclusions that "it is divisible by" some number. I don't think that you can conclude that something doesn't divide your number just because this test fails.

Concretely, your conclusion that 3|2^60-1 because of (x-1)|(x^n-1) is good.
I don't think you can conclude that 17 (does not divide) 2^60-1 because none of those factorizations yields 17.