Elementary Number Theory

Prove that if six people are riding together in an Evans Hall elevator, there is either a three-person subset of mutual friends (each knows the other two) or a three-person subset of mutual strangers (each knows neither of the other two).

Let $u_{m,n}$ be an array of numbers for $1 \leq m \leq N$ and $1 \leq n \leq N$. Suppose that $u_{m,n} = 0$ when $m$ is 1 or $N$, or when $n$ is 1 or $N$. Suppose also that

whenever $1 < m < N$ and $1 < n < N$. Show that all the $u_{m,n}$ are zero.

How many functions $f : \left\{ 1,2,3,4,5\right\} \rightarrow \left\{ 1,2,3,4,5\right\}$ have a range of size exactly 3?

Let $m \geq 0$ be an integer. Let $a_1, a_2, \ldots , a_m$ be integers and let

Show that if $d \geq 0$ is an integer then $f(x)^d/d!$ can be expressed in the form

where the $b_i$ are integers.

Let $f : [0,1] \rightarrow [0,1]$ be an increasing (not strictly increasing) function such that

whenever the $a_j$ are 0 or 2. Prove that there is a constant $C_0$ such that

for all $x,y \in [0,1]$.

Let $p$ be an odd prime. Let $Q(p)$ be the set of integers $a$, $0 \leq a \leq p-1$, for which the congruence

has a solution. Show that $Q(p)$ has cardinality $(p+1)/2$.

Let $p$ be an odd prime. If the congruence $x^2 \equiv -1 \pmod{p}$ has a solution, show that $p \equiv 1 \pmod{4}$.

Let $n \geq 2$ be an integer such that $2^n+n^2$ is prime. Prove that

Which rational numbers $t$ are such that

is an integer?

Show the denominator of $\binom {1/2}{n}$ is a power of 2 for all integers $n$.

Let $n$ be a positive integer.

Suppose that $n > 1$ is an integer. Prove that the sum

is not an integer.

Let $\gcd$ abbreviate greatest common divisor and $\operatorname {lcm}$ abbreviate least common multiple. For three nonzero integers $a,b,c$, show that

Let $a_1, a_2, \ldots , a_{10}$ be integers with $1 \leq a_i \leq 25$, for $1 \leq i \leq 10$. Prove that there exist integers $n_1, n_2, \ldots , n_{10}$, not all zero, such that

The number 21982145917308330487013369 is the thirteenth power of a positive integer. Which positive integer?

Determine the rightmost decimal digit of

Determine the last digit of

in the decimal system.

Show that one can represent the set of nonnegative integers, $\mathbb {Z}^{}_{+}$, as the union of two disjoint subsets $N_1$ and $N_2$ ($N_1 \cap N_2 = \emptyset$, $N_1 \cup N_2 = \mathbb {Z}^{}_{+}$) such that neither $N_1$ nor $N_2$ contains an infinite arithmetic progression.

Let $\varphi$ be Euler's totient function; so if $n$ is a positive integer, then $\varphi (n)$ is the number of integers $m$ for which $1 \leq m \leq n$ and $\gcd \left\{ n,m\right\} =1$. Let $a$ and $k$ be two integers, with $a > 1$, $k > 0$. Prove that $k$ divides $\varphi (a^k-1)$.

Determine the greatest common divisor of the elements of the set $\left\{ n^{13}-n \mid n \in \mathbb {Z}\right\}$.

For $n$ a positive integer, let $d(n)$ denote the number of positive integers that divide $n$. Prove that $d(n)$ is odd if and only if $n$ is a perfect square.

Which of the numbers $0,1,2,3,4,5,6,7,8,9$ occur as the last digit of $n^n$ for infinitely many positive integers $n$?

Let $N = 30030$, which is the product of the first six primes. How many nonnegative integers $x$ less than $N$ have the property that $N$ divides $x^3-1$?