Let $n$ be a positive integer. Prove that the numbers $$1^1, 3^3, 5^5, ..., (2n-1)^{2n-1}$$all give different remainders when divided by $2^n$.
Problem
Source: Switzerland - 2022 Swiss Final Round p2
Tags: number theory, remainder, divides
18.11.2022 00:22
Suppose two give the same remainder when divided by $2^n$ then there exist odd $a, b < 2n$ such that $b^b \equiv a^a$ mod $2^n$. WLOG $b > a$ and let $k = v_2(b - a)$. Note this gives $2^k | b - a \Rightarrow 2^k \leq b - a \leq (2n - 1) - 1 = 2n - 2 \leq 2^{n - 1}$ $\forall$ $n \in \mathbb{N}$ and so $k \leq n - 1 \Rightarrow k + 1 \leq n$. This means $b^b \equiv a^a$ mod $2^{k + 1}$. Since $\varphi(2^{k + 1}) = 2^k$ we have that $b^b \equiv b^a$ mod $2^{k + 1}$ as $2^k | b - a$ and $b$ is odd so it is indeed coprime with $2^{k + 1}$. Thus, $a^a \equiv b^b \equiv b^a$ mod $2^{k + 1} \Rightarrow 2^{k + 1} | b^a - a^a = (b - a)(b^{a - 1} + b^{a - 2}a + \dots + a^{a - 1})$. Since the right bracket is a sum of an odd number of odd terms as both $a$ and $b$ are odd we have that the right bracket is odd and so we must have $2^{k + 1} | b - a$ which is a contradiction as $v_2(b - a) = k$. Thus no $a, b$ exist so we are done.
18.11.2022 00:47
Thanks,alchimist_,I like your solution!
21.09.2024 20:00
We consider for a fixed $n$ the values of $a^a \mod 2^n$ for odd $a$. Assume for the sake of contradiction that we have $a^a \equiv b^b \mod 2^n$ for some odd $b < a$. We can interperet this as $ 2^n \vert a^a-b^b \Longleftrightarrow v_2(a^a-b^b) \geq n $ We note a couple properties of the p-adic valuation function: $ v_p(x) \neq v_p(y) \Rightarrow v_p(x+y) = min\{v_p(x), v_p(y)\} $ If $x$, $y$, $k$ odd then $v_2(x^k-y^k) = v_2(x-y)$ If $x$, $y$ odd and $k$ even then $v_2(x^k-y^k) = v_2(x+y) + v_2(x-y) + v_2(k) - 1$ by the LTE Lemma. Now consider: $ a^a - b^b = a^a - a^b + a^b - b^b = a^b(a^{a-b}-1) + a^b-b^b $ By the aforementioned properties we have $ v_2(a^a-b^b) = v_2(a^b(a^{a-b}-1) + a^b-b^b) = min\{ v_2(a^{a-b}-1), v_2(a^b-b^b) \} $ We have: $ v_2(a^b-b^b) = v_2(a-b) $ $ v_2(a^{a-b}-1) = v_2(a+1) + v_2(a-1) + v_2(a-b) - 1 $ We have $v_2(a+1) + v_2(a-1) - 1 > 0$, thus the two terms are unequal, with the latter clearly being larger, thus the value of the first is chosen. Thus: $ v_2(a^a - b^b) = v_2(a^b - b^b) = v_2(a-b) < n $ Because $a-b < 2^n$. This is a contradiction to our assumption and so we are done. (If i didn't make any typos)