Determine the greatest common divisor of the numbers: $$5^5-5, 7^7-7, 9^9-9 ,..., 2017^{2017}-2017,$$
Problem
Source: OLCOMA Costa Rica National Olympiad, Final Round, 2017 3.2
Tags: GCD, greatest common divisor, number theory
20.09.2021 20:54
gcd(5^5-5,7^7-7,11^11-11)=6, it is obvious 6 divides all of the numbers
20.09.2021 21:06
In module $2$: It is clear that they are all pairs In module $3$: The numbers are of the form $n^n -n$ If $n$ is multiple of $3$ If it complies! If $n$ is multiple of $3$ plus $1$: In factoring: $n(n^{n-1}-1)$ Since $n$ is odd then $n$ is pairs Then $n(n^{n-1}-1)$ is factorable $n-1$ is multiple of $3$ if $n$ is multiple of $3$ minus $1$ is analogous to the previous case Thus $gcd( 5 ^ 5-5, 7 ^ 7-7, 9 ^ 9-9, ..., 2017 ^ {2017} -2017)= 6$
25.01.2024 20:56
The gcd is a big bigger than that 6. we already know that $3 | n^n -n$ however, we can check that $8 | n^n - n$ (for odd $n > 4$). we factor $n^n -n = n(n^{n - 1} + 1)$, We use LTE for $p = 2$ and we get: $v_2(n^{n - 1} - 1) = v_2(n - 1) + v_2(n + 1) + v_2(n - 1) - 1$. We can see that both $n - 1$ and $n + 1$ are even, howver at least one of them should be divisible by 4 so we get $v_2(n^{n - 1} - 1) = v_2(n - 1) + v_2(n + 1) + v_2(n - 1) - 1 \geq 1 + 2 + 1 -1 = 3$ We can quickly verify that for $n = 11$ the equality holds. Then the gcd of the sequence is actually 24. Is possible to also check the value of $5^5 - 5$ to check the other primes that may appear and later on discard them
27.01.2024 22:29
Let $d=gcd(5^5-5,...,2017^{2017}-2017)$ $ (2k+1)^{2k+1}-(2k+1)=(2k+1) ( (2k+1)^{2k}-1)$ and $ (2k+1)^{2k} \equiv 1 \pmod {8}$ as square of odd number So $8|n^n-n$ for odd $n$ $(6k+1)^{6k+1}-(6k+1) \equiv 1^{6k+1}-1 \equiv 0 \pmod {3}$ $(6k+3)^{6k+3}-(6k+3) \equiv 0 \pmod {3}$ $(6k+5)^{6k+5}-(6k+5) \equiv 2^{6k+5}-2 \equiv 2( 4^{3k+2}-1) \equiv 0 \pmod {3}$ So $3|n^n-n$ for odd $n$ So $24|d$ $5^5-5=5*24*26 \to d| 5*24*26$ $7^7-7=7(7^6-1) \equiv 7(7^2-1) \equiv 1 \pmod {5}$ $7^7-7 =7(7^6-1) \equiv 7( 10^3-1) \equiv 12 \pmod {13}$ $19^{19}-19 \equiv 3^{19}-3 \equiv 3^3-3 \equiv 8 \pmod {16}$ And so $5,13,16 \not |d$ So $d=24$