# $(2k+1)^{4k+1} = (2k+1) \pmod {4k+2}$ . . . why?

Well, this must be simple but I seem to be dense at the moment. I checked heuristically for small $k$ $$(2k+1)^{4k+1} = (2k+1) \pmod {4k+2} \tag1$$ but couldn't prove that this is so in general.

For the other quarter of numbers, $$(2k)^{4k-1} = 0 \pmod {4k} \tag2$$ I found at least the (even more simple) solution.

So: is (1) true? and if, what is the proof?

-

(1)$(2k+1)^{4k+1}-(2k+1)=(2k+1)((2k+1)^{4k}-1)$ which is clearly divisible by $2k+1$

$(2k+1)^{4k}$ is odd, so, $(2k+1)^{4k}-1$ is even.

$\implies gcd(2(2k+1))\mid ((2k+1)^{4k+1}-(2k+1))$

(2) Let $2^r|| k,$ the highest power of $2$ in $4k$ is $r+2$ and in $(2k)^{4k-1}$ is $(r+1)(4k-1)$ which will be $\ge r+2$ if $k\ge 1$

For other primes $q>2$ , let $q^a||k$ the highest power of $q$ in $4k$ is $a$ and in $(2k)^{4k-1}$ is $a(4k-1)$ which will be $\ge a$ if $k\ge 1$

-
Well, it needed a bit to see this, but I got it now. Thanks! –  Gottfried Helms Oct 2 '12 at 15:58
@GottfriedHelms, I've added the 2nd answer, could you please check? –  lab bhattacharjee Oct 2 '12 at 16:03
well, that was not needed, because (it is obvious to me that) already with the exponent $2$ we get $(2k)^2 = 4k\cdot k = 0 \pmod{4k}$ and thus for all greater exponents. I'd also simplify your notation for the first proof, but since it is not too complicated we simply might leave it as it is... –  Gottfried Helms Oct 2 '12 at 16:07

For the first one, $(2k+1)^{4k+1} - (2k+1) = (2k+1) \left((2k+1)^{4k} - 1\right)$.

Note that $2 \vert \left((2k+1)^{4k} - 1 \right)$.

Hence, $4k+2 \vert (2k+1)^{4k+1} - (2k+1)$

For the second one. Note that for $k \geq 1$, $(2k)^{4k-1} = 2^3k^3 (2k)^{4k-4}$. Hence, in fact $$(2k)^{4k-1} \equiv 0\pmod{8k^3}$$

-

The number $(2k+1)^{4k+1}-(2k+1)$ is even so $$(2k+1)^{4k+1} \equiv (2k+1) \pmod 2 \ .$$ Since the $$(2k+1)^{4k+1} \equiv (2k+1) \pmod {2k+1}$$ is obvious and $\gcd{(2,2k+1)}=1$ we conclude that $$(2k+1)^{4k+1} \equiv (2k+1) \pmod {4k+2} \ .$$

-

Hint $\rm\,\ a,b\:|\:b^n-b\:\Rightarrow\:lcm(a,b)\:|\:b^n-b.\:$ You have $\rm\:a = 2,\ b\:$ odd, so $\rm\:lcm(a,b) = ab.$

Remark $\$ More generally if $\rm\:a,b\in\Bbb Z,\:$ and $\rm\:f(x)\in \Bbb Z[x]\:$ then

$$\rm a\:|\:f(b),\, b\:|\:f(0)\iff a,b\:|\:f(b)\iff lcm(a,b)\:|\:f(b)$$

Above is the special case $\rm\ f(x) =\, x^n - x.$

-