If $p$ is an odd prime, prove that \[{k \choose p}\equiv \left\lfloor \frac{k}{p}\right\rfloor \pmod{p}.\]

Click for solution That notation looks ugly, I will use $\mathbb{F}_p$ for the field with $p$ elements Lets work completely in $\mathbb{F}_p$. We look for the solutions $(x,y)$ of $x^2 = y^2+1$. One is given by $P=(1,0)$ and we use the method of secants to find all: We intersect lines $y=\lambda (x-1)$ through $P$ with slope $\lambda$ with the hyperbola $x^2-y^2=1$. This gives $x^2- (\lambda(x-1))^2=1 \iff (x-1)(x+1) - \lambda^2(x-1)^2 =0$, having $x=1$ (giving $y=0$, so resulting in the point $P$) as solution. The second solution is that of $(x+1) - \lambda^2(x-1) =0 \iff x=- \frac{1+\lambda^2}{1-\lambda^2}$. To $\lambda = \pm 1$, there corresponds no solution, but all other $\lambda$ give us some $x$ and thus also some $y$ in an unique way. If $\lambda, \lambda^\prime$ give the same $(x,y)$, then $\lambda (x-1) = y = \lambda^\prime (x-1)$, giving $\lambda=\lambda^\prime$ if $x \neq 1$. If $x=1$, we have $1=x=- \frac{1+\lambda^2}{1-\lambda^2} \iff 2=0$, contradiction. Conversely, every $(x,y) \neq P=(1,0)$ on the hyperbola gives us $\lambda = \frac{y}{x-1}$ by the same arguments. We see that this gives us a bijection between the slopes $\lambda \neq \pm 1$ and the points $\neq P$ on the hyperbola- Thus the set of points $(x,y)$ on the hyperbola equals $1$ (for $P=(1,0)$) plus the number of $\lambda \neq \pm 1$, thus in total equals $p-1$. If $y=0$, then $x^2=1 \iff x= \pm 1$, thus there are exactly two points with $y=0$. Similar, $x=0$ yields $y^2=-1$, having only (two) solutions if $p \equiv 1 \mod 4$. If $x,y \neq 0$, there are always exactly four points with the same value of $x^2$, namely $(\pm x , \pm y)$. It's also possible to get this result from http://www.problem-solving.be/pen/viewtopic.php?t=134 . Counting again, we get $\frac{p-1-4}{4}+1+1=\frac{p+3}{4}$ values for $x^2$ if $p \equiv 1 \mod 4$ and $\frac{p-1-2}{4}+1=\frac{p+1}{4}$ such values for $p \equiv -1 \mod 4$.

Suppose that $p$ is an odd prime. Prove that \[\sum_{j=0}^{p}\binom{p}{j}\binom{p+j}{j}\equiv 2^{p}+1\pmod{p^{2}}.\]

Click for solution Peter wrote: Suppose that $ p$ is an odd prime. Prove that \[ \sum_{i = 0}^{p}\binom{p}{i}\binom{p + i}{i}\equiv 2^{p} + 1\pmod{p^{2}}. \] I have a different approach leading to other possible generalizations (It is actually generalizing the Lemma from the second proof of Putnam 1991/B4 from the PEN bi-week file). We begin with a preliminary result (which actually does all the work): Theorem 1. Let $ x$, $ y$ be real numbers, and let $ p$, $ q$ be two positive integers. Then the following identity holds \[ \sum_{i = 0}^{p}{\binom{p}{i}\binom{q + i}{i}x^{p - i}y^{i}} = \sum_{i = 0}^{p}{\binom{p}{i}\binom{q}{i}(x + y)^{p - i}y^{i}. }\] Proof. Let $ m$, $ n$ be two real numbers. Consider the identity: \[ E: = \left[(x + y)m + y\right]^{p}(1 + m)^{q} = \left(\sum_{i = 0}^{p}{\binom{p}{i}\left(x + y\right)^{p - i}m^{p - i}y^{i}}\right)\left(\sum_{i = 0}^{q}{\binom{q}{i}m^{i}}\right). \] The coefficient of $ m^{p}$ from the right hand side of the identity is $ B: = \sum_{i = 0}^{p}{\binom{p}{i}\binom{q}{i}(x + y)^{p - i}y^{i}}$. On other hand, since \[ E = \left[mx + y(1 + m)\right]^{p}(1 + m)^{q} = \sum_{i = 0}^{p}{\binom{p}{i}x^{p - i}m^{p - i}y^{i}(1 + m)^{q + i}}, \] the coefficient of $ m^{p}$ is also equal to $ A: = \sum_{i = 0}^{p}{\binom{p}{i}\binom{q + i}{i}x^{p - i}y^{i}}$, and therefore $ A = B$, which proves Theorem 1. Returning to our problem, set $ x = y = 1$, and let $ q = p$ be a prime number. In this case, \[ \sum_{i = 0}^{p}\binom{p}{i}\binom{p + i}{i} = \sum_{i = 0}^{p}{\binom{p}{i}\binom{p}{i}2^{p - i} = 1 + 2^{p} + \sum_{i = 1}^{p - 1}{\binom{p}{i}^{2}2^{p - i} \equiv 2^{p} + 1\pmod{p^{2}}. }}\] This completes the proof of our problem.

Show that \[(-1)^{\frac{p-1}{2}}{p-1 \choose{\frac{p-1}{2}}}\equiv 4^{p-1}\pmod{p^{3}}\] for all prime numbers $p$ with $p \ge 5$.

Let $n$ be a positive integer. Prove that $n$ is prime if and only if \[{{n-1}\choose k}\equiv (-1)^{k}\pmod{n}\] for all $k \in \{ 0, 1, \cdots, n-1 \}$.

Click for solution We will regardless use that we can calculate with fractions $\mod n$ as long as the denominator is coprime to $n$. It's not hard to show that we always can do that. If $n$ is not prime, let $q<n$ be the smallest prime dividing $n=aq$: $\binom{n-1}{q}= \frac{(n-1) \cdot (n-1) \cdot ... \cdot (n-q)}{1 \cdot 2 \cdot ... \cdot q} =$ $= \frac{n-q}{q} \cdot \frac{n-1}{1} \cdot \frac{n-2}{2} \cdot ... \cdot \frac{n-q+1}{q-1} \equiv (a-1) \cdot (-1)^{q-1} \mod n$. But $a-1 \not \equiv -1 \mod n$ (this would yield $a \equiv 0 \mod n$, so $n|a|n$, wrong). If $n$ is prime, we do the same calculation to get $\binom{n-1}{q}= \frac{(n-1) \cdot (n-1) \cdot ... \cdot (n-q)}{1 \cdot 2 \cdot ... \cdot q} =$ $= \frac{n-1}{1} \cdot \frac{n-2}{2} \cdot ... \cdot \frac{n-q+1}{q-1} \cdot \frac{n-q}{q} \equiv (-1)^q \mod n$.

Prove that for $n\geq 2$, \[\underbrace{2^{2^{\cdots^{2}}}}_{n\text{ terms}}\equiv \underbrace{2^{2^{\cdots^{2}}}}_{n-1\text{ terms}}\; \pmod{n}.\]

Click for solution Taking a closer look at my proof in http://www.mathlinks.ro/viewtopic.php?p=849418.

Show that, for any fixed integer $\,n \geq 1,\,$ the sequence \[2, \; 2^{2}, \; 2^{2^{2}}, \; 2^{2^{2^{2}}}, \cdots \pmod{n}\] is eventually constant.

Click for solution Write $a_n=\underbrace{2^{2^{...^2}}}_{n \text{ times}}$, then $a_{n+1}=2^{a_n}$. Induction on $n$ (one could also use some straightforward way, but I think this way's nicer, and it kills topic 139, too): We show that it is constant beginning from the $n-1$-th term (or earlier): $n=1$ is clear. For any $n>1$, we write $n=2^m n^\prime$ with $n^\prime$ odd. The sequence $a_k$ clearly gets constantly $0 \mod 2^m$ for all $k \geq m \leq n-1$. So we are left to prove the same $\mod n^\prime$. By induction, the sequence gets constant $\mod \tilde n := \varphi(n^\prime) < n^\prime \leq n$. Thus there is $c$ such that for all $k \geq \tilde n-1$ we have $a_k \equiv c \mod \varphi(n^\prime)$. This gives $a_{k+1} = 2^{a_k} \equiv 2^c \mod n^\prime$ by the theorem of Euler-Fermat, meaning nothing else than constantness of the sequence for all $k>\bar n \leq n-1$, our result.

Somebody incorrectly remembered Fermat's little theorem as saying that the congruence $a^{n+1} \equiv a \; \pmod{n}$ holds for all $a$ if $n$ is prime. Describe the set of integers $n$ for which this property is in fact true.

Click for solution Lemma: It's the set of those squarefree $n$ with the following property: if the prime $p$ divides $n$, then so does $p-1$. Proof: If $p$ is some prime, $p^2 \nmid p^{n+1}-p$, thus $p^2 \nmid n$. If $p|n$, then we take a primitive root $a \mod p$ and get that $a^{n} \equiv 1 \mod p$, thus $(p-1)|n$ by the order-lemma. Conversely, if $n$ fulfills that properties and $p|n=(p-1)q$, then $a^{n+1} = a^{(p-1)q+1} \equiv a \mod p$ (even if $p|a$). Claim: all such numbers $n$ are $1,2,6,42,1806$. Proof: Testing these numbers to work using the lemma is easy, so we just show there are no others. Assume there are more than we claim to be and let $n=p_1 p_2 ... p_k$ with $p_1 < p_2 < ... < p_k$ be the smallest exception. Then the number $n^\prime=p_1 p_2 ... p_{k-1}$ still has the property by the lemma (all requirements are fulfilled again) and is in $M$. Additionally, $p_k-1|n^\prime$, leaving us to check that all numbers $d+1 $ with $d|1806=2\cdot 3 \cdot 7 \cdot 43$ and $d \not\in M$ are not prime. This is left to the reader

Characterize the set of positive integers $n$ such that, for all integers $a$, the sequence $a$, $a^2$, $a^3$, $\cdots$ is periodic modulo $n$.

Click for solution The sequence is periodic iff it is so $\mod$ all prime powers $p^k$ dividing $n$ (for all $a$). If $p^2|n$ for some prime $p$, then the sequence $p,p^2,p^3,... \equiv p,0,0,... \mod p^2$ is not periodic, thus $n$ has to be squarefree. If $p \nmid a$, then $a^{p-1} \equiv 1 \mod p$ and it is periodic. If $p|a$, then it's periodic, too. Thus the answer: exactly the squarefree $n$.

Show that there exists a composite number $n$ such that $a^n \equiv a \; \pmod{n}$ for all $a \in \mathbb{Z}$.

Click for solution Take $n=561= 3 \cdot 11 \cdot 17$, checking is trivial. My proposal (not easy): prove that there is an infinite number of composite $n$ with $a^n \equiv a \mod n$ for all integers $a$.

Let $p$ be a prime number of the form $4k+1$. Suppose that $2p+1$ is prime. Show that there is no $k \in \mathbb{N}$ with $k<2p$ and $2^k \equiv 1 \; \pmod{2p+1}$.

During a break, $n$ children at school sit in a circle around their teacher to play a game. The teacher walks clockwise close to the children and hands out candies to some of them according to the following rule. He selects one child and gives him a candy, then he skips the next child and gives a candy to the next one, then he skips 2 and gives a candy to the next one, then he skips 3, and so on. Determine the values of $n$ for which eventually, perhaps after many rounds, all children will have at least one candy each.

Click for solution We identify the children with the residues $\mod n$. It starts with turn $0$ when child $0 \mod n$ gets a candy. In turn $k$ the teacher gives a candy to the child $1+2+...+k =\frac{k(k+1)}{2} \mod n$. We are thus asked for what $n$ the map $\sigma :k \mapsto \frac{k(k+1)}{2} \mod n$ is surjective. If $p$ is an odd prime dividing $n$, we would need that $\sigma$ is surjective $\mod p$. But $\sigma \mod p$ only depends on the residue classes $\mod p$. By $\sigma(-1) \equiv \sigma(0) \mod p$ we get that it's not injective, thus not surjective. Thus $n$ is a power of $2$, $n=2^k$. We show that it works for all those $n$: We want $k$ with $\frac{k(k+1)}{2} \equiv a \mod 2^k \iff (2k+1)^2 \equiv 8a+1 \mod 2^{k+3}$ for all $a$. But it's well known that $\mod$ any power of two, exactly the residues $\equiv 1 \mod 8$ are those that are quadratic residues, thus we are done.

Suppose that $m>2$, and let $P$ be the product of the positive integers less than $m$ that are relatively prime to $m$. Show that $P \equiv -1 \pmod{m}$ if $m=4$, $p^n$, or $2p^{n}$, where $p$ is an odd prime, and $P \equiv 1 \pmod{m}$ otherwise.

Click for solution We first observe that this is true for $m=1,2$. Let now $m\geq 3$. If some $x$ with $(x,m)=1$ has an multiplicative inverse $x^{-1}$ with $x\not\equiv x^{-1}\pmod m$, they drop out of $P$, so we have \[P=\prod_{\substack{1\leq x \leq m\\ (x,m)=1}}x\equiv \prod_{\substack{1\leq x\leq m\\ x^{2}\equiv 1 \bmod m}}x \equiv \prod_{\substack{1\leq x \leq \lfloor \frac{m}{2}\rfloor\\ x^{2}\equiv 1 \bmod m}}-x^{2}\equiv \prod_{\substack{1\leq x \leq \lfloor \frac{m}2 \rfloor\\ x^{2}\equiv 1 \bmod m}}-1 \equiv (-1)^{\frac{a(m)}{2}}\pmod m\] where $a(n)$ denotes the number of $1\leq x \leq m$ so that $x^{2}\equiv 1 \pmod m$. Lemma 1: $a(1)=1, a(2)=1, a(4)=2$. Proof: Inspection. $\Box$ Lemma 2: $a(2^{k})=4$ for $k\geq 3$. Proof: We have \[x^{2}\equiv 1 \pmod{2^{k}}\\ \Leftrightarrow (x-1)(x+1)\equiv 0 \pmod{2^{k}}\\ \Leftrightarrow x\equiv-1,+1 \pmod{2^{k-1}}\\ \Leftrightarrow x\equiv 1, 2^{k-1}-1,2^{k-1}+1, 2^{k}-1 \pmod{2^{k}}\] $\Box$ Lemma 3: $a(p^{k})=2$ for all odd primes $p$. Proof: We have \[x^{2}\equiv 1\pmod{p^{k}}\\ \Leftrightarrow (x-1)(x+1)\equiv 0\pmod{p^{k}}\\ \Leftrightarrow x\equiv-1,+1 \pmod{p^{k}}\] $\Box$ Lemma 4: $a$ is multiplicative, ie $a(mn)=a(m)a(n)$ for all coprime $m,n$. Proof: Since $m$ and $n$ are coprime, we have $x^{2}\equiv 1 \pmod{mn}$ if and only if $x^{2}\equiv 1\pmod m$ and $x^{2}\equiv 1 \pmod n$. Let $y_{1},\ldots,y_{a(m)}$ be those residues modulo $m$ so that $y_{i}^{2}\equiv 1\pmod m$ and let $z_{1},\ldots,z_{a(n)}$ be those residues modulo $n$ so that $z_{i}^{2}\equiv 1 \pmod n$. Then, by the chinese remainder theorem, we have $x^{2}\equiv 1\pmod{mn}$ if and only if $x\equiv y_{i}\pmod m$ and $x\equiv z_{j}\pmod n$ for some $1\leq i\leq a(m)$ and $1\leq j \leq a(n)$. Clearly, we have $a(m)a(n)$ possibilities to choose such $i,j$ and since we get another $x$ modulo $mn$ for each such possibilities, we obtain $a(mn)=a(m)a(n)$. $\Box$ Corollary 1: $a(m)$ is not divisible by $4$ if and only if $m=1,2,4,p^{k}, 2p^{k}$ where $p$ is an odd prime and $k$ is a positive integer. This solves the problem.

Let $\Gamma$ consist of all polynomials in $x$ with integer coefficients. For $f$ and $g$ in $\Gamma$ and $m$ a positive integer, let $f \equiv g \pmod{m}$ mean that every coefficient of $f-g$ is an integral multiple of $m$. Let $n$ and $p$ be positive integers with $p$ prime. Given that $f,g,h,r$ and $s$ are in $\Gamma$ with $rf+sg\equiv 1 \pmod{p}$ and $fg \equiv h \pmod{p}$, prove that there exist $F$ and $G$ in $\Gamma$ with $F \equiv f \pmod{p}$, $G \equiv g \pmod{p}$, and $FG \equiv h \pmod{p^n}$.

Click for solution That's a way to state Hensel's lemma for $\mathbb{Q}_{p}$. Proof of the theorem: We inductively construct polynomials $F_{n}, G_{n}$ such that $F_{n}G_{n}\equiv h \mod p^{n}$. For $n=1$, we take $F_{1}=f$ and $G_{1}=g$. For $n\geq 1$, we try to find polynomials $f_{n},g_{n}$ such that we can set $F_{n+1}=F_{n}+p^{n}f_{n}, G_{n+1}=G_{n}+p^{n}g_{n}$. The only thing we need is \[h \equiv F_{n+1}G_{n+1}\equiv F_{n}G_{n}+p^{n}(f_{n}G_{n}+g_{n}F_{n}) \mod p^{n+1},\] thus \[h_{n}\equiv f_{n}G_{n}+g_{n}F_{n}\equiv f_{n}g+g_{n}f \mod p,\] where $h_{n}= \frac{h-F_{n}G_{n}}{p^{n}}\in \Gamma$. By $rf+sg \equiv 1 \mod p$ we get $h_{n}=rfh_{n}+sgh_{n}\mod p$, thus setting $f_{n}=rh_{n}, g_{n}=sh_{n}$ gives our result.

Determine the number of integers $n \ge 2$ for which the congruence \[x^{25}\equiv x \; \pmod{n}\] is true for all integers $x$.

Let $n_{1}, \cdots, n_{k}$ and $a$ be positive integers which satify the following conditions: for any $i \neq j$, $(n_{i}, n_{j})=1$, for any $i$, $a^{n_{i}} \equiv 1 \pmod{n_i}$, for any $i$, $n_{i}$ does not divide $a-1$. Show that there exist at least $2^{k+1}-2$ integers $x>1$ with $a^{x} \equiv 1 \pmod{x}$.

Click for solution Ok, new try (after the first was spam): Let $p_i$ be the smallest prime dividing $n_i$ ($n_i=1$ is not possible because $1|a-1$). Claim: $p_i|a-1$, especially $p_i < n_i$ (otherwise $n_i=p_i|a-1$). Assume the contrary: Let $q_i$ be any prime dividing the order of $a \mod p_i$ (the order is $>1$ if $p_i \nmid a-1$). As we have $p_i|n_i|a^{n_i}-1$ and $p_i|a^{p_i-1}-1$, we get $q_i|n_i, (p_i-1)$, contradiction since $q_i<p_i$ divides $n_i$. For each $i$ we can choose one number from $c_i \in \{1,p_i,n_i\}$ and look at $m=\prod_{i=1}^k c_i$. We have $a^{c_i} \equiv 1 \mod c_i$ independet what $c_i$ we took, thus also $a^{m} = \left( a^{c_i} \right)^\frac{m}{c_i} \equiv 1 \mod c_i$. But the $c_i$ are coprime, giving $a^m \equiv 1 \mod m$ and we always get different $m$ by different choices of $c_i$. In total we got a total number of $3^k$ such $m$ (where $m=1$ was counted). But the inequality $3^k-1 \geq 2 \cdot 2^k-2$ is trivial to check to be true.

Determine all positive integers $n \ge 2$ that satisfy the following condition; For all integers $a, b$ relatively prime to $n$, \[a \equiv b \; \pmod{n}\Longleftrightarrow ab \equiv 1 \; \pmod{n}.\]

Click for solution Let $n$ have that property. Then $a \equiv a \mod n$ gives $a^2 \equiv 1 \mod n$ for all $a$ coprime to $n$. Since $2^2 \not\equiv 1 \mod 5$ (and because we always replace $2$ by some residue coprime to $n$ and $\equiv 2 \mod 5$) we get $5 \nmid n$. Especially we are forced to have $5^2 \equiv 1 \mod n$, thus $n|24$. It's trivial that $n=3$ and $n=8$ work, thus by the chinese remainder theorem the same holds for $n=24$. This imediately implies the property for the divisors of $24$, too.

Determine all positive integers $n$ such that $ xy+1 \equiv 0 \; \pmod{n} $ implies that $ x+y \equiv 0 \; \pmod{n}$.

Click for solution Taking any $a$ coprime to $n$, we find $b \equiv -a^{-1} \mod n$ such that $ab\equiv -1\mod n$, thus $a+b \equiv 0 \mod n$, giving $a^2 \equiv 1 \mod n$. We just used $a$ coprime to $n$, thus we conclude like in http://www.problem-solving.be/pen/viewtopic.php?t=150 .

Let $p$ be a prime number. Determine the maximal degree of a polynomial $T(x)$ whose coefficients belong to $\{ 0,1,\cdots,p-1 \}$, whose degree is less than $p$, and which satisfies \[T(n)=T(m) \; \pmod{p}\Longrightarrow n=m \; \pmod{p}\] for all integers $n, m$.

Click for solution As $ T(x) = x^{p - 2}$ shows, there is a polynomial of degree $ p - 2$ with the required property. Thus we only have to exclude ones with degree $ p - 1$: Let $ T(x) = \sum_{k = 0}^{p - 1} a_k x^k$. Define $ s_k = \sum_{i = 1}^p i^k$, then it's known that $ p|s_k$ if $ 0\leq k \leq p - 2$ (posted by me on PEN somewhere) and $ s_{p - 1} \equiv - 1 \mod p$ (simply little Fermat). As $ T$ is supposed to be injective as a function $ \mathbb Z / p \mathbb Z \to \mathbb Z / p \mathbb Z$, it is bijective. Especially $ 0 \equiv \sum_{i = 1}^p i \equiv \sum_{i = 1}^p T(i) = \sum_{i = 1}^p \sum_{k = 0}^{p - 1} a_k i^k \mod p$. Using what we know, we get $ 0 \equiv \sum_{k = 0}^{p - 1} a_k \sum_{i = 1}^p i^k = \sum_{k = 0}^{p - 1} a_k s_k \equiv - a_{p - 1} \mod p$. This gives $ p|a_{p - 1}$, thus $ a_{p - 1} = 0$, in other words: $ T$ has degree strictly less than $ p - 1$. [thanks ZeTaX for rewriting nicely]

Let $a_{1}$, $\cdots$, $a_{k}$ and $m_{1}$, $\cdots$, $m_{k}$ be integers with $2 \le m_{1}$ and $2m_{i}\le m_{i+1}$ for $1 \le i \le k-1$. Show that there are infinitely many integers $x$ which do not satisfy any of congruences \[x \equiv a_{1}\; \pmod{m_{1}}, x \equiv a_{2}\; \pmod{m_{2}}, \cdots, x \equiv a_{k}\; \pmod{m_{k}}.\]

Click for solution We look at residues $a \mod m= m_1 m_2 ... m_k$ and call $a$ "forbidden" iff $a \equiv a_1 \mod m_i$ for some $i$. We clearly have $m_i \geq 2^{i-1} m_1$ for all $i$. The total number of forbidden residues $\mod m$ by some fixed $i$ is $\frac{m}{m_i}$. Thus the total number of forbidden residues $\mod m$ is at most $\sum_{i=1}^k \frac{m}{m_i} < \frac{m}{m_1} \cdot \sum_{i=1}^k \frac{1}{2^{i-1}} < \frac{2m}{m_1} \leq m$. So there is some residue class that is not forbidden, giving that all it's infinitely many members don't satisfy any of these congruences.

Show that $1994$ divides $10^{900}-2^{1000}$.

Click for solution Clearly divisible by $2$, leaving us to show that $997$ divides it. But $10^{900} \equiv 1000^{300} \equiv (-3)^{300} = (-27)^{100} \mod 997$ and $2^{1000} \equiv 1024^{100} \equiv 27^{100} = (-27)^{100} \mod 997$, thus we are done.

Determine the last three digits of \[2003^{2002^{2001}}.\]

Click for solution Let $\phi(\cdot)$ be Euler totient function. Since 2003 is co-prime to 10 and $\phi(1000)=400$, we have \[2003^{2002^{2001}}\equiv 3^{2002^{2001}\bmod 400}\pmod{1000}.\] Note that $400=16\cdot 25.$ It is clear that $2002^{2001}\equiv 0\pmod{16}.$ On the other hand, since $\phi(25)=20,$ \[2002^{2001}\equiv 2^{2001\bmod 20}\equiv 2\pmod{25}.\] Using CRT, we have $2002^{2001}\bmod 400=352.$ Therefore, \[2003^{2002^{2001}}\equiv 3^{352}\equiv 241\pmod{1000}.\]

Prove that $1980^{1981^{1982}} + 1982^{1981^{1980}}$ is divisible by $1981^{1981}$.

Click for solution General: $n^n | (n-1)^{n^{n+1}}+(n+1)^{n^{n-1}}$ if $n$ is odd and squarefree. Proof: If $p$ is an odd prime and $p^k|a-b$ ($k \geq 1$), we get that $p^{k+m}|a^{s p^m}-b^{s p^m}$ for all $m,s$. Set $a=(n-1)^{n^2}$ and $b=-(n+1)$, then $a^{n^{n-1}}+(-b)^{n^{n-1}}$ is the desired number. Since $a-b = (n-1)^{n^2} + (n+1) \equiv (-1)^\text{odd} +1 = 0 \mod n$, thus $p|a-b$ for all primes $p|n$. This now gives: $p^n|a^{s p^{n-1}}-b^{s p^{n-1}}=(n-1)^{n^{n+1}}+(n+1)^{n^{n-1}}$ with $s=\left(\frac{n}{p}\right)^{n-1}$. the result follows.

Let $p$ be an odd prime of the form $p=4n+1$. Show that $n$ is a quadratic residue $\pmod{p}$. Calculate the value $n^{n}$ $\pmod{p}$.

Click for solution Recall that $a$ is a $k$-th power iff $a^\frac{p-1}{\gcd(p-1,k)} \equiv 1 \mod p$. We show that $n$ is a fourth power $\mod p$: We have $16n \equiv -4 \equiv (2i)^2 \mod p$, thus we want that $2i$ is a square $\mod p$ (here $i$ is such that $i^2 \equiv -1 \mod p$, existing by $p \equiv 1 \mod 4$). - If $p \equiv 1 \mod 8$, then $2$ is a quadratic residue and $i$ is, too, the latter by $i^{p-1}2 = (-1)^\frac{p-1}4 = 1 \mod p$. - If $p \equiv 5 \mod 8$, then $2$ is nonsquare $\mod p$ and $i$ is, too, the latter by $i^\frac{p-1}2 \equiv (-1)^\frac{p-1}4 = -1 \not\equiv 1 \mod p$. In both cases, $2i$ is a quadratic residue, thus there is an $a$ with $a^4 \equiv n \mod p$. Or shorter: $(1+i)^4 \equiv (2i)^2 \equiv -4 \mod p$, giving the same result with $a=1+i$. This solves directly a. (and shows more), but also b. follows: $n^n \equiv (a^4)^\frac{p-1}4 = a^{p-1} \equiv 1 \mod p$.