Author |
Topic: gcd puzzle (Read 457 times) |
|
NickH
Senior Riddler
Gender: 
Posts: 341
|
What is the greatest common divisor of the following set of numbers?
{11n + 10n5 + 80n - 1 | n = 1, 2, 3...}
|
|
 IP Logged |
Nick's Mathematical Puzzles
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
 |
Re: gcd puzzle
« Reply #1 on: Apr 8th, 2003, 9:46am » |
 Quote  Modify
|
OK, I know the answer is 100, and can prove it by breaking down the series and analyzing the how the last two digits of each of the terms change, but I lack the vocabularly to express it. Particularly the 10n5 term.
|
|
IP Logged |
|
|
|
wowbagger
Uberpuzzler
 
Gender:
Posts: 727
|
|
Re: gcd puzzle
« Reply #2 on: Apr 8th, 2003, 11:52am » |
Quote Modify
|
As the divisibility by 100 is quite obvious if one calculates the first few terms, I won't hide the rest of this post.
To show the divisibility by one hundred, write the number sn in the given set modulo 100 (implicit in "="):
sn = (10+1)n + 10n5 + 80n - 1
= 10n + 1 + 10n5 + 80n - 1
= 10n5 + 90n
The last digit is already proven to be zero. So let's divide by ten and look at the last but one digit (mod 10):
sn/10 = n5 + 9n
= n5 - n = n (n2-1) (n2+1)
=: f(n)
Now, it suffices to examine f(n) for 1 <= n <= 9. This is so because f(i*10+j) = f(j) (mod 10). As it turns out, f(1), ..., f(9) are all divisible by 10.
(Probably this isn't the best way to show this part, but it is the first I tried.)
I know I haven't proved that the gcd isn't greater than 100, but I haven't considered that part yet and my time is up for now.
|
| « Last Edit: Apr 8th, 2003, 11:53am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: gcd puzzle
« Reply #3 on: Apr 8th, 2003, 4:26pm » |
Quote Modify
|
That the gcd isn't greater than 100 is trivial: 100 is the value for n=1 !
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: gcd puzzle
« Reply #4 on: Apr 18th, 2003, 10:06am » |
Quote Modify
|
Here's an induction-like solution...
Let f(n) = 11n + 10n5 + 80n - 1.
f(1) = 100. For n >= 1:
f(n+1) - f(n) = 10*11n + 10(5n4 + 10n3 + 10n2 + 5n + 1) + 80.
f(n+1) - f(n) = 10*(1+10)n + 100k1 + 90, for an integer k1, since n4 + n is always even.
f(n+1) - f(n) = 10(1 + 10k2) + 100k1 + 90, for an integer k2.
f(n+1) - f(n) = 100k, for an integer k.
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print