Spanning set

Let $S = \{0,1,2,\dots,10\}$.

A set of numbers $A \subset S$ is called "spanning" if the set $\{ x, x+1, x+2, x+3 \mod 11 | x \in A \} = S$.

And a set of numbers $B \subset S$ is called "potentially spanning" if there is an integer $k$ such that the set $\{kb \mod 11 | b \in B \}$ is spanning.

Prove that every subset of $S$ with four elements are potentially spanning, and prove that there exists a subset of $S$ with three elements that is not potentially spanning.

Solution First, we show that there is a subset of three elements that is not potentially spanning.

Note that for a set to be spanning, it has to be $\{c,c+4, c+8\}$ for some $c$ (here we assume everything is modulo 11, so we don't write it for notational simplicity). This is because the maximum distance between two adjacent element is 4, so the distances between 3 elements must be 4+4+3 (or its rotation).

Now we claim that a set $\{x,y,z\}$ is potentially spanning if and only if there exists $r \neq 0$ and $s$ such that $\{x,y,z\} = \{r+s, 2r+s, 3r+s \mod 11\}$. First, clearly if a set is spanning, then all of its "rotations" are also spanning sets. Likewise, if a set is potentially spanning, then all of its rotations are also potentially spanning. So wlog we may assume that $s=0$. Then the set $\{r,2r,3r\}$ is potentially spanning because we can always take $k = 4r^{-1} \mod 11$ so that $\{kr,2kr,3kr\} = \{4,8,12=1\}$ a spanning set. The inverse modulo is guaranteed to exist because 11 is prime and $r \neq 0$.

Now the other direction. Suppose $\{x,y,z\}$ is potentially spanning, such that $\{kx,ky,kz\}$ is spanning. As we've established above, it must have form $\{c,c+4, c+8\}$ for some $c$. Thus we can take $r = 4k^{-1} \mod 11$ and $s = (c-4)k^{-1} \mod 11$ so that $\{k(r+s),2kr,3kr\} = \{4+ks,8+ks,12+ks\} = \{c,c+4,c+8\}$.

So we have shown that the potentially spanning sets are generated by (and only by) the number of $(r,s)$ pairs we can choose. There are 10 choices for $r$ and 11 for $s$, so there are at most 110 potentially spanning sets. We say at most because some choices of $r$ and $s$ may "collide" (result in the same spanning triplet). However, there are ${11 \choose 3} = 165$ possible triplets, so there are some triplets that are not generated by the $(r,s)$ construction above and thus not potentially spanning.

Now we show that a subset $B = \{b_1,b_2,b_3,b_4\}$ is always potentially spanning. Note that if any three of $b_i$s form a potentially spanning triplet then $B$ is potentially spanning. In particular, if $B$ contains an arithmetic sequence modulo 11 then $B$ is potentially spanning. So we assume that $B$ is free from arithmetic progression.

Now let $d_i = b_{i+1} - b_i$ (of course we mean $b_5 = b_1$. Then among all four $d_i$s, let $d$ be the maximal distance. If the maximal distance is 4, then we are done because $B$ itself is spanning. So we assume that the maximal distance is at least 5. Wlog, we may assume that this maximal distance is $d_4$ and that $b_1 = 0$. So this means $0=b_1 < b_2 < b_3 < b_4 = 11-d$ and $b_i$ must not contain arithmetic sequence. It's easy to see that the only possible combinations are:

Case 1: $d=5$, so $0=b_1 < b_2 < b_3 < b_4 = 6$. The only combinations are $\{0,1,4,6\}, \{0,1,5,6\},\{0,2,5,6\}$. All the other combinations contain an arithmetic sequence. But in the first two cases, we can take $k=8$ to get: $\{0,4,8,10\}, \{0,4,7,8\}$ which contains arithmetic sequence thus potentially spanning, and for the third case we can take $k=3$ to get $\{0,4,6,7\}$ which is spanning.

Case 2: $d=6$, so $0=b_1 < b_2 < b_3 < b_4 = 5$. The only combinations are $\{0,1,4,5\}$ and $\{0,2,3,5\}$. We can take $k=4$ to get $\{0,4,5,9\}$ and $k=2$ to get $\{0,4,6,10\}, both spanning sets.

Case 3: $d=7$, so $0=b_1 < b_2 < b_3 < b_4 = 5$. The only combination is $\{0,1,3,4\}$. We can take $k=5$ to get $\{0,4,5,9\}$, a spanning set.

And there is no way to have $d > 7$ and still fitting $b_2$ and $b_3$ without getting an arithmetic progression. So our proof is complete.

Sum of products of 3

Let $p>3$ be a prime number, and let $S={2,3,\dots,p-1}$ Let $X = \sum_{ i < j < k \in S} ijk$, prove that $X + 1$ is divisible by $p$.

Solution

Because $p$ is odd, let $p = 2m+1$. First we calculate $1^2 + \dots + (p-1)^2 \mod p$. We do this by realizing that $1^2 = (p-1)^2 \mod p, 2^2 = (p-2)^2 \mod p$ and so on. Every term will have a "pair", so the sum is: $$1^2 + \dots + m^2 + (m+1)^2 + \dots + (p-1)^2$$ $$ \equiv 2 (1 + \dots + m^2) \mod p$$ $$ \equiv m(m+1)(2m+1) \equiv 0 \mod p$$ because $2m+1 = p$. This means that $2^2 + \dots + (p-1)^2 \equiv -1 \mod p$

Next we calculate $1^3 + \dots + (p-1)^3 \mod p$. We do this by realizing that $p = 1 + (p-1) | 1^3 + (p-1)^3, p=2+(p-2) | 2^3+(p-2)^3$ and so on. Like above, each term will have a pair that it cancels out with. Thus $1^3 + \dots + (p-1)^3 \equiv 0 \mod p$, so $2^3 + \dots + (p-1)^3 \equiv -1 \mod p$.

Now we also have that $1+\dots + (p-1) \equiv 0 \mod p$, so $2 + \dots + (p-1) \equiv -1 \mod p$. From this, we have: $$ 2\sum_{i < j \in S} ij \equiv (-1)^2-(-1) \equiv 2 \mod p $$ $$\sum_{i < j \in S} ij \equiv 1 \mod p$$ because $p$ is odd.

Now, for any real numbers $a_1, \dots, a_n$, let us define the following variables: $$A = a_1 + \dots + a_n$$ $$B = \sum_{i < j} a_i a_j$$ $$C = \sum_{i \neq j } a_i^2 a_j$$ $$D = \sum_{i < j < k} a_i a_j a_k$$ $$E = a_1^2 + \dots + a_n^2$$ $$F = a_1^3 + \dots + a_n^3$$ Then we have: $$AB = (a_1+\dots+a_n)(a_1a_2 + a_1a_3 + \dots + a_{n-1}a_n) = C + 3D$$ The identity from middle to right is because for each $a_i$ in $A$, it's either paired with $a_ia_j$ or $a_j a_k$ in B. If it's paired with $a_i a_j$ then it would contribute towards $C$, otherwise it would contribute towards $3D$. Likewise, each term in $C$ and $3D$ can be traced back to $AB$. Each term $a_i^2 a_j$ in $C$ comes from $a_i$ in $A$ and $a_i a_j$ in $B$. Each term $3a_i a_j a_k$ in $3D$ comes from three sources: $a_i$ in $A$ and $a_j a_k$ in $B$ and its permutations. To further convince ourselves, $A$ has $n$ terms, and $B$ has $n(n-1)/2$ terms, so $AB$ has $n^2(n-1)/2$ terms. $3D$ has $n(n-1)(n-2)/2$ terms and $C$ has $n(n-1)$ terms, so altogether they have $n^2(n-1)/2$ terms.

Furthermore: $$C = a_1^2(A-a_1) + a_2^2(A-a_2) + \dots + a_n^2(A-a_n) = AE - F$$ So: $$3D = AB-C = F + AB-AE$$ This identity holds for any real numbers $a_i$, and it's based on pure algebraic manipulation. We can apply this identity to our set $S$. We already know that $F \equiv -1, A \equiv -1, B \equiv 1, E \equiv -1 \mod p$. From there, we have $3D \equiv -3 \mod p$, which means $(3D+3)$ is divisible by $p$. Because $p > 3$ then $D+1$ is divisible by $p$.

non-injective power mapping

Suppose $p$ is a prime and $f(a) = a^m$ is defined for $a$ that are relatively prime to $p$, then prove that $f$ is injective if and only if $m$ does not divide $p-1$.

a,b,c fraction integer

Given positive integers $a,b,c$ such that
$$\frac{a}{b} + \frac{b}{c} + \frac{c}{a}$$
is also an integer, show that
$$\frac{a^2b^2}{c},\frac{b^2c^2}{a}, \frac{c^2a^2}{b}$$
are all cubic numbers.

Circular Locker Problem

From a friend's brother:

There are 1000 lockers and 1000 students. The lockers are arranged in a circle, all closed. The 1st student opens all the lockers. The 2nd student closes every other locker. The 3rd student goes to every 3rd locker. If it’s open he closes it, if it’s closed, he opens it. When he gets to locker #999, he continues to locker #2 and continues until he reaches a locker that he has already touched. The 4th student goes to every 4th locker: again, if it’s closed, he opens it, if it’s open, he closes it. Every student after that does the same, until student #1000, who will obviously just open or close locker #1000. After they are all finished, which lockers will be open?

Solution


First, let's think about what happens when student $n$ does his turn.

If $n$ is relatively prime to 1000, that is, $n$ does not contain any factor of 2 or 5, then $n$ will touch all the lockers exactly once. For example, student #3 will go touching lockers 3,6,...,999,2,5,...,998,1,4,7,...,997,1000. In this case student $n$ behaves exactly like student #1.

If $n$ is a multiple of $2$ or $5$, then let $d = \gcd(1000,n)$ Student $n$ touches locker $m$ if and only if $d$ divides $m$. For example, if $n=16$, then $d = 8$. Student #16 will go touching lockers 16,32,...,992,8,24,...,1000, which are exactly all multiples of 8. In this case, student $n$ behaves exactly like student #8.

Now, how many students have numbers that are NOT relatively prime to 1000? Such students must have numbers in the form of $n = 2^a 5^b$ We can enumerate the possibilities:

If $b=0$, then the student numbers are: 2,4,8,16,32,64,128,256,512, for a total of 9 students. Remember that students #16,32,...,512 behave exactly like student #8,and there are 6 of them, so it's equivalent to student #8 going 6 extra times. Their effects cancel out pairwise. So we only need to consider the effects of students #2,4,8.

If $b=1$, then the student numbers are: 5,10,20,40,80,160,320,640, for a total of 8 students. Remember that students #80,...,640 behave exactly like student #40,and there are 4 of them, so their effects cancel out pairwise. So we only need to consider the effects of students #5,10,20,40.

If $b=2$, then the student numbers are: 25,50,100,200,400,800, for a total of 6 students. Remember that students #400,8000 behave exactly like student #200, so their effects cancel out. So we only need to consider the effects of students #25,50,100,200.

If $b=3$, then the student numbers are: 125,250,500,1000.

If $b=4$, then the student number is: 625, which behaves like student #125, and thus cancels the effect of student #125.

So in total, there are 9+8+6+4+1 = 28 numbers that are not relatively prime to 1000, so there are an even numbers of students that are relatively prime. Each of these students touches all lockers exactly once, so their effects again cancel out pairwise. Thus, the student numbers that we need to consider are: (grouped by their largest factor of 2):
5,25
2,10,50,250
4,20,100,500
8,40,200,1000

In order to determine if locker $n$ is closed or open, find all numbers above that divides $n$. If there are even such numbers, then the locker is close, otherwise it's open.

For example, 120 = 3 x 5 x 8, so 120 is divisible by 2,4,8, 5,10,20,40. That means locker #120 is open.

For a more explicit list of open lockers, the following are the open lockers:
1. Lockers with numbers (not divisible by 5 or divisible by 25), and (divisible by 2 but not by 4, or divisible by 8).
2. Lockers with numbers divisible by 5 but not 25, and (divisible by 4 but not by 8).

Number of solutions to modular equation

Prove that there are infinitely many prime numbers $p$ such that there are exactly $p^2$ integer triples $(x,y,z)$ such that $0 \leq x,y,z < p$ and $x^2+y^2 - 2010z^3$ is divisible by $p$.

Solution

We will first show that any prime that has form $p = 6k-1$ and does not divide 2010 satisfies the given condition.

First, let $p$ be such prime. Suppose there are $a,b \in \{ 1, \dots, p-1 \}$ such that $a^3 \equiv b^3 \mod p$.

Since $b^{p-1} \equiv 1 \mod p$ then let $c \equiv ab^{p-2} \mod p$, so that we have $bc \equiv a \mod p$.

Then $b^3c^3 \equiv a^3 \equiv b^3 \mod p$ which means $b^3c^3 \equiv b^3 \mod p$ which then means $c^3 \equiv 1 \mod p$ (since $(b,p) = 1$).

Because $c^{p-1} = c^{6k-2} \equiv 1 \mod p$ and $c^{6k-3} = c^{3(2k-1)} \equiv 1 \mod p$, then we must have $c \equiv 1 \mod p$, which means $a \equiv b \mod p$.

In summary, we've shown that $a^3 \equiv b^3 \Rightarrow a \equiv b \mod p$. This means that the set $\{1^3, \dots, p^3 \} \mod p$ is the same as set $\{ 1, \dots, p \} \mod p$. So given any arbitrary $x$ and $y$, we can find exactly one $z$ such that $z^3 \equiv 2010^{-1} (x^2+y^2) \mod p$. Since there are $p^2$ possible pairs for $(x,y)$, then there are also $p^2$ possible triples for $(x,y,z)$.

Now we show that there are infinitely many primes of the form $6k-1$ which would mean that there must be infinitely many primes of the form $6k-1$ that do not divide 2010.

Note that any prime above 3 must have form $6k+1$ or $6k-1$. If there are only finite number of primes of the form $6k-1$, say $p_1, p_2, \dots, p_n$, consider the number $N = 6p_1p_2 \dots p_n - 1$.
For each $i$, $p_i$ does not divide $N$ because otherwise $p_i$ would also have to divide 1, a contradiction. So $N$ is not divisible by any of the $p_i$s, which means all prime factors of $N$ must be of the form $6k+1$. That means, $N \equiv 1 \mod 6$, a contradiction.

a,b,c integers and cubic number

Suppose $a,b,c$ are positive integers such that $\frac{a}{b} + \frac{b}{c} + \frac{c}{a}$ is an integer. Prove that $abc$ is a cubic number.

Solution

We have $ab^2 + bc^2 + ca^2 = kabc$ for some k.

Let $d = \gcd(a,b,c)$. We can replace $a,b,c$ by $a/d, b/d, c/d$ respectively and the problem does not change. Thus, without loss of generality, we may assume that $d = 1$.

Let $p$ be a prime that divides $abc$, which means $p$ divides at least one of $a,b,c$. We also know that $p$ cannot divide all three, since $d = 1$.

If $p$ divides exactly one of $a,b,c$, for example $a$, then $ab^2, ca^2, kabc$ are all divisible by $p$, but not $bc^2$. Impossible. Thus, $p$ must divide exactly two of $a,b,c$.

Suppose $p$ divides $a$ and $b$. Furthermore, let $x$ be the largest integer such that $p^x$ divides $a$. Likewise, let $y$ be the largest integer such that $p^y$ divides $b$.

Since $ab^2, bc^2, kabc$ are all divisible by $b$, then so is $ca^2$. Thus $y \leq 2x$.

Since $ab^2, ca^2, kabc$ are all divisible by $a$, then so is $bc^2$, Thus $y \geq x$, which means $x \leq y \leq 2x$.

Now, since $ab^2, ca^2, kabc$ are all divisible by $p^{2x}$, then so is $bc^2$, which means $y \geq 2x$.

Therefore, $y = 2x$, which means that the degree of $p$ in the factorization of $abc$ is $x+y = 3x$.

For each prime $p$ that divides $abc$, it must occur as a cubic number in its prime factorization. Thus $abc$ is a cubic number.

A non-trivial example is $a=1,b=2,c=4$.

Sequence with prime number

Suppose $p$ is a prime number greater than 2, and $m$ is a natural number. Let $a_n$ be sequences defined by:
$a_1 = 1$
$a_2 = m$
$a_{n+2} = \frac{a_{n+1}^2 +p}{a_n}, n = 1,2,...$

Determine all values of $m$ such that $a_n$ is an integer for all $n$.

Finite Prime Set

Let $P$ be a finite set of primes. Define $m(P)$ as the largest number of consecutive integers each of which is divisible by a prime in $P$.
Let $|P|$ denote the size of $P$ and $\min(P)$ to be the smallest element in $P$.

Prove that:
1. $m(P) \geq |P|$
2. $m(P) = |P|$ if and only if $\min (P) > |P|$

Solution

Let $s = |P|$. We proceed by constructing $s$ consecutive integers which are each divisible by a prime in $P$. Indeed, the following system has a solution, according to Chinese Remainder Theorem:
$x+1 \equiv 0 \pmod {p_1}$
$x+2 \equiv 0 \pmod {p_2}$
...
$x+s \equiv 0 \pmod {p_s}$

Second part:
Suppose we have $s < \min(P)$ and that we have $s+1$ consecutive integers all divisible by some $p_i$: $x, x+1, x+2, ... , x+s$. Let $p_1 = \min(P)$.

For each $p_i$, it can only divide at most one of the above-mentioned integers. For if it divides $x+a$ and $x+b$ then it also divides $|a-b| \leq s < p_1$, a contradiction (since $p_1$ is the smallest prime in $P$).
So $m(P) \leq s$. But it's been shown that $m(P) \geq s$, so $m(P) = s$.

Now suppose we have $s \geq \min(P)$. We will show $s+1$ consecutive integers such that each is divisible by a prime in $P$, which then establishes $m(P) > s$.
Let $k = \min(P)$.
Again, we set up a system of equations as described above, but we choose the ordering of $p_i$s such that $p_k = k$. The rest can be arbitrary ordering. This is always possible if $s \geq k$.
According to CRT, there is a solution of $s$ consecutive integers that satisfy the above system of equations. But then we also have $x = x+k - k$ divisible by $p_k = k$. So together with $x$, they form $s+1$ consecutive integers.

Solution: Happy Saint Math Trick's Day

Original problem: http://dharmath.blogspot.com/2010/03/happy-saint-math-tricks-day.html

This problem is inspired by this comic.

Prove that the trick in the comic always works. In other words, if $p$ is a prime number greater than 3, prove that $p^2 + 14 \equiv 3 \mod 12$

Solution

$p^2 + 14 \equiv 3 \mod 12$ means that $p^2+11$ is divisible by 12, which means that $p^2+11-12 = p^2-1$ is divisible by 12.

If $p$ is a prime number greater than 3, then $p$ is odd. This means that $p$ divided by 4 has remainder either 1 or 3. In both cases, $p^2$ divided by 4 has remainder 1, which means $p^2-1$ is divisible by 4.

If $p$ is a prime number greater than 3, then $p$ divided by 3 has remainder either 1 or 2. In both cases, $p^2$ divided by 3 has remainder 1, which again means $p^2-1$ is divisible by 3.

Since $p^2-1$ is divisible by both 3 and 4, it is divisible by 12.

Happy Saint Math Trick's Day

This problem is inspired by this comic.

Prove that the trick in the comic always works. In other words, if $p$ is a prime number greater than 3, prove that $p^2 + 14 \equiv 3 \mod 12$

Solution: http://dharmath.blogspot.com/2010/03/solution-happy-saint-math-tricks-day.html

KBB3 Problem 1

Find the smallest prime number that divides $54^{54} + 55^{55} + 56^{56}$

KBB2 Problem 7

Prove that for any $n > 1$, the polynomial

$P(x) = 2008x^n + 7x + 56$

cannot be factored into two non-trivial integer polynomials.

(A polynomial is non-trivial if its highest degree is greater than one)