# Tag Info

41

Rewrite $k^3 + 3k^2 + 2k = k(k+1)(k+2)$. Since exactly one of the three factors must be divisible by 3, the product must also.

18

HINT: Try factoring! Another hint:

17

To check if values $p(k)$ of the polynomial $p$ with integer coefficients is divisible by $m$ for all integer $n$, you only to check that $$p(k) \equiv 0 \pmod m, \; \forall k \in {0,\ldots,n-1}\tag{1}$$ or equivalently $$m \mid p(k), \; \forall k \in {0,\ldots,n-1}$$ So if $p(k)=k^3+3k^2+2k$ we have $p(0)=0$ is divisible by $3$ $p(1)=6$ is divisible ...

13

If $k$ is a multiple of $3$, then the statement is obviously true. Then suppose that $k$ is not a multiple of $3$. Since $k$ and $3$ are coprime, $$k^2 \equiv 1\pmod 3$$ by Euler's theorem. Then $$k^3+3k^2+2k \equiv 3k\equiv 0. \pmod 3$$ Therefore $k^3+3k^2+2k$ is divisible by $3$.

6

Yet another approach: simply plugging in values gives $$0^3 = 0 \mod 3$$ $$1^3 = 1 \mod 3$$ $$2^3 = 2 \mod 3$$ In other words, $k^3 = k \mod 3$. Therefore, $k^3 + 3k^2 + 2k = 3k^2 + 3k = 0 \mod 3$

5

Just to be different. If $k \in \mathbb Z$ then $k = 3m + i$ where $i =$ either $0, 1,$ or $-1$ and $m \in \mathbb Z$. So \begin{align*} k^3 + 3k^2 + 2k &=(3m + i)^3 + 2(3m + i)+ 3k^2 \\ &= 3^3m^3 + 3 \cdot 3^2m^2 \cdot i + 3 \cdot 3m \cdot i^2 + i^3 + 2 \cdot 3m + 2i + 3k^2 \\ &= i^3 + 2i + 3\big[3^2m^3 + 3^2m^2i + 3m \cdot i^2 + k^2\big] ...

5

Avoiding the factoring solution (since that's a special case - elegant, but not general): We can ignore the $3k^2$ in $k^3+3k^2+2k$, so we just want to know if $k^3+2k=k(k^2+2)$ is divisible by $3$. Either $k$ is divisible by $3$, or it is not, in which case $k^2 \equiv 1 \mod 3$ Then $k^2+2\equiv 0 \mod 3$.

5

Alternatively, consider induction. The base case is clear. Assuming it holds for some $k$, $(k+1)^3+3 (k+1)^2+2 (k+1) = 3(k+2) (k+1) + (k^3+3 k^2+2 k)$ and so it holds for $k+1$.

5

Hint: By the Euler-Fermat theorem we know $45^{\varphi(4)} = 45^{2} \equiv 1 \mod 4$. By the Euler-Fermat theorem we also know $45^{\varphi(17)} = 45^{16} \equiv 1 \mod 17$ It is clear that $45 \equiv 0 \mod 3$ . The Chinese Remainder Theorem gives us now $45^{16} \equiv 69 \mod 204$. Hence $45^{17} \equiv 69 \cdot 45 = 3105 \equiv 45 \mod 204$.

5

$x = 3^n, y = 2^n$ $$3 x^2 + x y - 4 y^2 = (3x + 4y)(x - y)$$

4

Write the polynomial this way: $$k^3 + 3k^2 + 2k = 6 \binom{k}{1} - 12 \binom{k}{2} + 6\binom{k}{3}$$ But then it becomes immediately obvoius that $$k^3 + 3k^2 + 2k = 6 \left[ \binom{k}{1} - 2 \binom{k}{2} + \binom{k}{3} \right]$$ is divisible by $6$, and in particular divisible by $3$. This isn't just a cute trick. It is actually a much more general ...

4

Let $S = \{1, 2, 3, \ldots, 3n - 2, 3n - 1, 3n\}$. Let \begin{align*} A & = \{k \in S \mid k \equiv 0 \pmod{3}\}\\ B & = \{k \in S \mid k \equiv 1 \pmod{3}\}\\ C & = \{k \in S \mid k \equiv 2 \pmod{3}\} \end{align*} Observe that $|A| = |B| = |C| = n$. We can choose three numbers from $S$ in the following ways: Choose $3$ elements of $A$, ...

3

This is not transitive because $(32, 8) , (8,4) \in R$ but $(32,4) \notin R$.

3

If $m\mid 8n+7$ and $m\mid 6n+5$, then $$m\mid 3(8n+7)-4(6n+5)=1,$$ so $1=mk$ for some $k\in\mathbb Z$, so $m=\pm 1$.

2

By Fermat's Little theorem $k^3\equiv k\pmod{3}$, therefore: $$k^3+\underbrace{3k^2}_{\equiv 0}+\underbrace{2k}_{\equiv -k}\equiv k^3-k\equiv 0\pmod{3}$$

2

Hint: $45\equiv1\pmod4\implies45^n\equiv1$ $45\equiv0\pmod3\implies45^m\equiv0$ $45\equiv11\pmod{17}$ and $17\equiv1\pmod{16}$ and $17^n\equiv1$ $\implies11^{17^{17}}\equiv11\pmod{17}$ Now apply CRT

2

$z$ is even, so $2$ divides $2 y - z$ and $3 z + 2 x$. Modulo $3$ you have $0 \equiv 8 x - 10 y + 27 z \equiv 2 x - y$, so $3$ divides $2 x - y$. Modulo $5$ you have $0 = -8x - 27 z \equiv 2 x + 3 z$, so $3 z + 2 x$ is divisible by $5$.

2

Hint: use the Fermat's little theorem

2

I'm not going to give a full answer to this question, but I'll give some idea how you might go about it. You need to reduce $5^{2015}$, $2^{2017}$, and $5^{670}$ modulo 17. Now, by Fermat's little theorem, $5^{16} \equiv 1 \pmod{17}$. Since $2015 = 16 \times 125 + 15$, this gives you $5^{2015} = (5^{16})^{125} \times 5^{15} \equiv 1^{125} 5^{15} ... 2 By Little Fermat,$5^{2015}\equiv 5^{2015\bmod 16}=5^{-1}\mod17$. Now Bézout's relation:$\;7\cdot 5-2\cdot 17=1$, shows$5^{-1}\equiv 7\mod 17$. Similarly,$2^{2017}\equiv 2^{2017\bmod16}=2$and$5^{670}\equiv 5^{670\bmod16}=5^{-2}\equiv7^2\equiv -2\mod17$. Thus $$3\cdot 5^{2015}+2^{2017}\cdot 5^{670}\equiv 3\cdot7+2\cdot (-2)=17\equiv 0\mod17.$$ 1 HINT:$45^{17}\equiv45\pmod{204}$1 As$(45,204)=3$let us start with$45^{17^{17}-1}\pmod{\dfrac{204}3}$Using Carmichael function,$\lambda(204)=16$and$17\equiv1\pmod{16}\implies17^{17}\equiv1\implies45^{17^{17}-1}\equiv1\pmod{68}$More generally,$a^{17^n-1}\equiv1\pmod{68}$if$(a,68)=1$and$n$is a positive integer Now,$45^{17^{17}-1}\cdot45\equiv1\cdot45\pmod{68\cdot45}$... 1 Factorise$k^3 + 3k^2 + 2k = k(k+1)(k+2)$. Let$k\equiv 2 \mod 3$. Then$k+1\equiv 0 \mod 3$and$k+2\equiv 1 \mod 3$. So,$k(k+1)(k+2)\equiv 0*1*2 \mod 3$. Therefore$k(k+1)(k+2)\equiv 0 \mod 3$. 1 Suppose we had to choose$3$things out of$k+2$things, there are$k+2$ways of choosing the first one,$k+1$ways of choosing the next, and$k$ways of choosing the third. But we've overcounted by a factor of six, because any three things could be chosen in six different orders. So $$(k+2)(k+1)k=k^3+3k^2+2k$$ divides by six and hence also by three. 1 Number of solutions to$a+b+c=k$where$a,b,c$are positive integers is$\binom{k-1}{2}\$. So the number of ways to choose is $$\sum_{k=1}^n\binom{3k-1}{2}={n\over2}(3n^2-1)$$ Edit: As JMoravitz notes below this counting accounts for ordered triples from the given set rather than subsets.

Only top voted, non community-wiki answers of a minimum length are eligible