Hot answers tagged

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.


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, \begin{equation} k^2 \equiv 1\pmod 3 \end{equation} by Euler's theorem. Then \begin{equation} k^3+3k^2+2k \equiv 3k\equiv 0. \pmod 3 \end{equation} 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

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


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