wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> gcd puzzle
        
(Message started by: NickH on Apr 7^th, 2003, 1:15pm)

Title: gcd puzzle
Post by NickH on Apr 7^th, 2003, 1:15pm

What is the greatest common divisor of the following set of numbers?

{11ⁿ + 10n⁵ + 80n - 1 | n = 1, 2, 3...}

Title: Re: gcd puzzle
Post by aero_guy on Apr 8^th, 2003, 9:46am

OK, I know the answer is [hide]100[/hide], 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 10n⁵ term.

Title: Re: gcd puzzle
Post by wowbagger on Apr 8^th, 2003, 11:52am

As the divisibility by [hide] 100 [/hide] 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 s_n in the given set modulo 100 (implicit in "="):
s_n = (10+1)ⁿ + 10n⁵ + 80n - 1
= 10n + 1 + 10n⁵ + 80n - 1
= 10n⁵ + 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):
s_n/10 = n⁵ + 9n
= n⁵ - n = n (n²-1) (n²+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.

Title: Re: gcd puzzle
Post by Icarus on Apr 8^th, 2003, 4:26pm

That the gcd isn't greater than 100 is trivial: 100 is the value for n=1 !

Title: Re: gcd puzzle
Post by NickH on Apr 18^th, 2003, 10:06am

Here's an induction-like solution...

Let f(n) = 11ⁿ + 10n⁵ + 80n - 1.
f(1) = 100. For n >= 1:
f(n+1) - f(n) = 10*11ⁿ + 10(5n⁴ + 10n³ + 10n² + 5n + 1) + 80.
f(n+1) - f(n) = 10*(1+10)ⁿ + 100k₁ + 90, for an integer k₁, since n⁴ + n is always even.
f(n+1) - f(n) = 10(1 + 10k₂) + 100k₁ + 90, for an integer k₂.
f(n+1) - f(n) = 100k, for an integer k.