Easy gcd
A sequence { x n } n = 0 ∞ is defined by x 1 = 1 and x n + 1 = 2 x n 2 − 1 for all n ∈ N + .
Determine the greatest common divisor of 2 0 1 8 ! and x 2 0 1 8 ! .
The answer is 1.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
I‘m sorry ,Sir, but you'd mistaken x n + 1 = 2 x n 2 − 1 for x n + 1 = 2 x n − 1 (though it dosen't matter...)
We can prove by induction that x n = 1 for all n ∈ N . Given that x 1 = 1 , assuming that the claim is true for x n , then x n + 1 = 2 x n 2 − 1 = 1 , proving that x n = 1 for all n ∈ N . Therefore, g cd ( 2 0 1 8 ! , x 2 0 1 8 ! ) = g cd ( 2 0 1 8 ! , 1 ) = 1 .