Find GCD

Find the greatest common divisor of the following numbers.

{ 2 13 2 , 3 13 3 , 4 13 4 , , 1 3 13 13 } \left \{ 2^{13}-2,\ 3^{13}-3,\ 4^{13}-4, \dots ,\ 13^{13}-13 \right \}

2730 8190 630 126

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.

2 solutions

We can express n 13 n n^{13}-n as ( n 1 ) n ( n + 1 ) ( n 2 n + 1 ) ( n 2 + 1 ) ( n 2 + n + 1 ) ( n 4 n 2 + 1 ) (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 ) (n-1)n(n+1) is always divisible by 3 ! = 6 3!=6 , ( n 1 ) n ( n + 1 ) ( n 2 + 1 ) (n-1)n(n+1)(n^2+1) is always divisible by 6 × 5 = 30 6\times 5=30 , ( n 1 ) n ( n + 1 ) ( n 2 + 1 ) ( n 2 n + 1 ) ( n 2 + n + 1 ) (n-1)n(n+1)(n^2+1)(n^2-n+1)(n^2+n+1) is always divisible by 30 × 7 = 210 30\times 7=210 , and the entire product is always divisible by 210 × 13 = 2730 210\times {13}=2730 . (Using the standard divisibility conditions). Therefore n 13 n n^{13}-n is divisible by 2730 2730 for all positive integral values of n n . Hence the required GCD is 2730 \boxed {2730}

Paramananda Das
Dec 26, 2019

Let d d be the g.c.d.

Now d n 13 n d | {n^{13}-n} n = 2 , . . , 13 \forall n =2,..,13

2 13 2 = 2 × 5 × 7 × 9 × 13 2^{13}-2 = 2 \times 5 \times 7 \times 9 \times 13

= > d ( 2 × 5 × 7 × 9 × 13 ) => d | (2 \times 5 \times 7 \times 9 \times 13)

Observe that 2 , 3 , 5 , 7 , 13 2,3,5,7,13 all divide n 13 n {n^{13}-n} n = 2 , . . , 13 \forall n =2,..,13 { using Euler Totient function}

and 9 9 doesn't divide 3 13 3 {3^{13}-3} as 3 12 1 {3^{12}-1} is not divisible by 3 3 .

Hence d = 2 × 3 × 5 × 7 × 13 = 2730 d = 2 \times 3 \times 5 \times 7 \times 13 = \boxed{2730} .

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.

Isaac YIU Math Studio - 1 year, 5 months ago

Yeah , you are right, my fault. 3 12 1 3^{12}-1 gives remainder 2 2 when divided by 3 3

Paramananda Das - 1 year, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...