MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 added 78 characters in body
• The transcendence of $2^{\sqrt{2}}$ and $e^{\pi}$: Gel'fond's proof. (Assuming some basic complex analysis).

• Nathanson's problem: show that $3^n \nmid 5^n-2$ for $n > 1$. (This involves the $p$-adic analog of the above topic).

• More elementary (see also Yuhao Huang's answer above): the determination of $F_p \mod{p}$ for the Fibonacci sequence (i.e., periodic modulo $5$), as a consequence of the congruence $2\cos{(px)} \equiv 2\cos^p(x) \mod{p\mathbb{Z}[\cos{x}]}$ and the formula $(1+\sqrt{5})/4 = \cos{(2\pi/10)}$. This I think is a good, algebraic point of entry into quadratic reciprocity (obviously, it is equivalent to the splitting law for $\mathbb{Q}(\sqrt{5})$). A key point of course is to explain that $1/p$ is not a sum of roots of 1 (or, if one prefers, that is not an albgebraic integer), so that the congruence may be exploited appropriately. Interpretation as a "Fermat's little theorem" for $\mathbb{Q}(\sqrt{5})$.

• Related: Exhibit a formula showing that $\sqrt{N} \in \mathbb{Q}\big( e^{2\pi i/4N} \big)$, and perhaps use this to conclude that the residue of $N^{\frac{p-1}{2}} \mod{p}$ only depends on the residue of $p \mod{4N}$.

• $\mathbb{Q}$ has no unramified extensions.

• There is always a prime between $n$ and $2n$: Erdos' elementary proof.

• The Wolstenholme-Jacobsthal congruence $\binom{np}{mp} \equiv \binom{n}{m} \mod{p^3}$ using the "Stirling formula" for the $p$-adic $\Gamma$-function. Or combinatorial proofs of such congruences. (Or indeed, any other congruence from A. Granville's "Arithmetic Properties of Binomial Coefficients.")

• Completely elementary: Zsygmondy's theorem and applications. (Here is one: find all integer solutions of $a^n = b^n + c^k$ subject to $|c| \leq n$).

• If $a^n - 1 \mid b^n - 1$ for all $n > 0$, then $b = a^j$. If $a4^n + b6^n + c9^n$ is a perfect square for each $n$, then $(a,b,c) = (r^2,2rs,s^2)$. Solve, and generalize both!

1 [made Community Wiki]
• The transcendence of $2^{\sqrt{2}}$ and $e^{\pi}$: Gel'fond's proof. (Assuming some basic complex analysis).

• Nathanson's problem: show that $3^n \nmid 5^n-2$ for $n > 1$. (This involves the $p$-adic analog of the above topic).

• More elementary (see also Yuhao Huang's answer above): the determination of $F_p \mod{p}$ for the Fibonacci sequence (i.e., periodic modulo $5$), as a consequence of the congruence $2\cos{(px)} \equiv 2\cos^p(x) \mod{p\mathbb{Z}[\cos{x}]}$ and the formula $(1+\sqrt{5})/4 = \cos{(2\pi/10)}$. This I think is a good, algebraic point of entry into quadratic reciprocity (obviously, it is equivalent to the splitting law for $\mathbb{Q}(\sqrt{5})$). A key point of course is to explain that $1/p$ is not a sum of roots of 1 (or, if one prefers, that is not an albgebraic integer), so that the congruence may be exploited appropriately. Interpretation as a "Fermat's little theorem" for $\mathbb{Q}(\sqrt{5})$.

• Related: Exhibit a formula showing that $\sqrt{N} \in \mathbb{Q}\big( e^{2\pi i/4N} \big)$, and perhaps use this to conclude that the residue of $N^{\frac{p-1}{2}} \mod{p}$ only depends on the residue of $p \mod{4N}$.

• $\mathbb{Q}$ has no unramified extensions.

• The Wolstenholme-Jacobsthal congruence $\binom{np}{mp} \equiv \binom{n}{m} \mod{p^3}$ using the "Stirling formula" for the $p$-adic $\Gamma$-function. Or combinatorial proofs of such congruences. (Or indeed, any other congruence from A. Granville's "Arithmetic Properties of Binomial Coefficients.")

• Completely elementary: Zsygmondy's theorem and applications. (Here is one: find all integer solutions of $a^n = b^n + c^k$ subject to $|c| \leq n$).

• If $a^n - 1 \mid b^n - 1$ for all $n > 0$, then $b = a^j$. If $a4^n + b6^n + c9^n$ is a perfect square for each $n$, then $(a,b,c) = (r^2,2rs,s^2)$. Solve, and generalize both!