Find the greatest common divisor of the following numbers.
{ 2 1 3 − 2 , 3 1 3 − 3 , 4 1 3 − 4 , … , 1 3 1 3 − 1 3 }
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.
Let d be the g.c.d.
Now d ∣ n 1 3 − n ∀ n = 2 , . . , 1 3
2 1 3 − 2 = 2 × 5 × 7 × 9 × 1 3
= > d ∣ ( 2 × 5 × 7 × 9 × 1 3 )
Observe that 2 , 3 , 5 , 7 , 1 3 all divide n 1 3 − n ∀ n = 2 , . . , 1 3 { using Euler Totient function}
and 9 doesn't divide 3 1 3 − 3 as 3 1 2 − 1 is not divisible by 3 .
Hence d = 2 × 3 × 5 × 7 × 1 3 = 2 7 3 0 .
Your proof is ok but there is a mistake that is in the 6th line, the reason of 9 doesn't divide 3^13-3 is not because 3^12-1 is even (Example: 12 is even, but it is divisible by 3), and it should just be simple like 3 doesn't divide 3^12-1 like that.
Yeah , you are right, my fault. 3 1 2 − 1 gives remainder 2 when divided by 3
Problem Loading...
Note Loading...
Set Loading...
We can express n 1 3 − n as ( n − 1 ) n ( n + 1 ) ( n 2 − n + 1 ) ( n 2 + 1 ) ( n 2 + n + 1 ) ( n 4 − n 2 + 1 ) . Of these, ( n − 1 ) n ( n + 1 ) is always divisible by 3 ! = 6 , ( n − 1 ) n ( n + 1 ) ( n 2 + 1 ) is always divisible by 6 × 5 = 3 0 , ( n − 1 ) n ( n + 1 ) ( n 2 + 1 ) ( n 2 − n + 1 ) ( n 2 + n + 1 ) is always divisible by 3 0 × 7 = 2 1 0 , and the entire product is always divisible by 2 1 0 × 1 3 = 2 7 3 0 . (Using the standard divisibility conditions). Therefore n 1 3 − n is divisible by 2 7 3 0 for all positive integral values of n . Hence the required GCD is 2 7 3 0