Prove that 1991 divides ((1900^1990) - 1))
- Thread starter Yale
- Start date
Steven G
Elite Member
- Joined
- Dec 30, 2014
- Messages
- 14,598
What have you tried? Can you tell us what it means for a|b?
a|b means a divides b. In other words, a is a factor of b.
Since 1991 = 11 * 181
If I can prove 11 divides 19001990 - 1 and 181 divides 19001990 - 1, 1991 must divide 19001990 - 1.
I have proved 11|x10 - 1 for x which is any natural number but not a multiple of 11, the way I used was not elegant at all, any better proof would be very useful.
x10- 1 = (x5 + 1)(x5 - 1) = (x + 1)(x4 - x3 + x2 - x + 1)(x - 1)(x4 + x3 + x2 + x + 1)
Suppose there are 11 consecutive natural numbers as follow:
x-4 x-3 x-2 x-1 x x+1 x+2 x+3 x+4 x+5 x+6
Since there must be one and only one number in these 11 number to be a multiple of 11, to prove 11|x10- 1 , we can show that all these 11 numbers are factors of x10- 1 and hence 11 must be a factor of x10- 1.
We can change these 11 numbers by adding or subtracting 11x4 or 11x3 or 11x2 or 11x or 11, since these numbers are multiples of 11, they do not affect the divisibility.
If none of x , x+1, x-1 are multiples of 11: (otherwise we are done)
x4 - x3 + x2 - x + 1 = x4 - x3 + x2 - x - 10 = (x-2)(x3 + x2 +3x + 5) = (x-2)(x3 + x2 - 8x - 6) = (x-2)(x+3)(x2 -2x - 2) = (x-2)(x+3)(x2 +9x + 20) = (x-2)(x+3)(x+4)(x+5)
If none of x , x+1, x-1, x-2, x+3, x+4, x+5are multiples of 11: (otherwise we are done)
(x+2)(x+6)(x-3)(x-4) = (x2 +8x +12)(x2 -7x + 12) = (x2 -3x +1)(x2 +4x + 1) = x4 + 4x3 + x2 - 3x3 -12x2 -3x + x2 + 4x + 1 = x4 + x3 -10x2 + x + 1 = x4 + x3 + x2 + x + 1
therefore, if one of the 12 numbers is multiple of 11, x10- 1 is a multiple of 11 when x itself is not a multiple of 11.
Since there must be a number which is multiple of 11 in these 11 consecutive natural number, the statement 11|x10- 1 for x is not multiple of 11 has been proved.
This is what I have done so far, when x = (1900199), 11|19001990-1
But I do not know how to deal with 181|19001990-1
I am sorry that the question was quoted mistakenly and could not be done. The actual question is easy, thank you for your help anyway.
The actual question is to prove 1991|19901990-1
I mistakenly quoted 1991|19001990-1
Therefore, I know the solution now
19901990-1 has a factor of 1990 +1 which equals to 1991, because
19901990-1 = (1990995+1)(1990995-1)
and xn+1 has a factor of x + 1 when n is an odd number, since 995 is odd,1991 must be a factor of 1990995+1 and hence 19901990-1.
Thus 1991 divides 19901990-1.