Polynomial and divisibility

Find an integer polynomial $P(x)$ with the lowest degree that satisfies the following:

$P(x)$ is divisible by $x^2+x+1$

$P(x)+3$ is divisible by $x^{2017} -1$

Solution

Let $Q(x) = x^2+x+1$ and $R(x) = x^{2016} + \dots + 1$. It's easy to show that $Q$ and $R$ are relatively prime.

The LCM for both divisors is thus $(x-1)Q(x)R(x)$ which has degree 2019.

Now if $P$ and $P'$ both satisfy the problem statement, then $P-P'$ must be divisible by $(x-1)Q(x)R(x)$.

On the other hand, if $P$ satisfies the problem statement, then $P + A(x).(x-1)Q(x)R(x)$ also satisfies the problem statement for any integer polynomial $A(x)$.

Therefore, we can find at most one $P(x)$ with degree less than 2019, because if there were two such polynomials, their difference must be divisible by $(x-1)Q(x)R(x)$ but that difference has degree less than 2019, so the difference must be zero. That one polynomial is our answer.

To find it: let $t$ be the root of $Q(x)$. We want to find $P(x)$ such that:

$$P(x)+3 = S(x).(x-1).R(x)$$ for some $S(x)$, with $S(x) = ax+b$. We know that it's possible for $S$ to be a linear function because we've established that there exists a $P$ with degree less than 2019, and $R$ has degree 2016.

$$P(t) + 3 = (at+b).(t-1).R(t)$$

$P(t) = 0$ because $P(x)$ is divisible by $Q(x)$ and $Q(t) = 0$.

$R(t) = t^{2016} + \dots + t + 1 = 1$ because every 3 consecutive terms in $t^{2016} + \dots + t$ sum to zero (because $Q(t) = 0$).

So: $$ 3 = (at+b)(t-1)$$ $$at^2 + (b-a)t - b-3 = 0$$ $$a(-t-1) + (b-a)t - b-3 = 0$$ $$ (b-2a)t=a+b+3$$

Solving for the system:$b-2a = 0, a+b+3 = 0$ gives us: $a = -1, b= -2$ so $S(x) = -(x+2)$

Plugging in to the equations, we find:

$$P(x) = -(x+2)(x^{2017}-1) - 3 = -x^{2018} - 2x^{2017} + x -1 = -x^2(x^{2016}-1) -2x(x^{2016}-1) -( x^2+x+1) $$

Each term in the right-most expression is divisible by $Q(x)$ because $(x^{2016}-1)$ is divisible by $x^3-1$ so $P(x)$ is also divisible by $Q(x)$

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.

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.

Polynomial and divisibility

A sequence of polynomials $P_i(x)$ are defined as follows:
$P_1(x) = 1$
$P_2(x) = 1$
$P_{n+2}(x) = (x+2)P_{n+1}(x) - P_n(x), n=1,2,\dots$

Prove that for all $n > 1$, $P_n(x)^2 + x$ is divisible by $P_{n-1}(x)$

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.

Factorial and power of 2

Credit for this problem goes to Peter Macko.

If $n$ is a positive integer, prove that $(2^n)! $ is divisible by $2^{2^n-1}$ and that its quotient is an odd number.

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)

KBB2 Problem 6

An integer is called homogenous if its decimal representation consists of 1 number. For example, 11 and 222 are homogenous. Prove that there are infinitely many homogeneous numbers that are divisible by 2008.