Tag Info

Hot answers tagged

17

Write $n=3r+q$ with $q\in\{0,1,2\}$. Then $$ n^2+4=9r^2+6rq+q^2+4=(9r^2+6rq+3)+q^2+1. $$ The expression in the parentheses is divisible by $3$ whereas inspecting the three possibilities for $q$ reveals that $q^2+1$ is never divisible by $3$.


12

Hint: Show that one of the numbers is a multiple of $5$. One way to do that: Write $x=5k+r$.


11

Hint: $$ n^2(n^2+1)(n^2−1)\cong n^2(n^2-4)(n^2−1) = (n-2)(n-1)(n^2)(n+1)(n+2) $$


9

Whether or not things are "undefined" largely depeneds on what framework you are working in. If we are working in the naturals, we might say that $3-5$ is undefined. There are many systems where it makes sense to assign $\frac{n}{0}$ some value. In this particular example, it is defined to be complex infinity, which can be thought of as follows: suppose we ...


9

You can write \begin{align*} 7^{2048} - 1 &= 7^{2048} - 1^{2048} \\ &= (7^{1024} + 1)(7^{512} + 1)(7^{256} + 1)(7^{128} + 1)(7^{64} + 1)(7^{32} + 1)(7^{16} + 1)(7^{8} + 1)(7^{4} + 1)(7^{2} + 1)(7 + 1)(7-1) \end{align*} For all $k \geq 2$, $7^{2^k} + 1 \equiv (-1)^{2^k} + 1 \equiv 2 \mod 4$, so each term of the form $(7^{2^k} + 1)$ has only one ...


8

For any integer $n$ we have, $$n\equiv\{0,1,2\}\pmod3\implies n^2\equiv \{0,1,4\}\equiv \{0,1,1\}\equiv\{0,1\}\pmod3\\ \implies n^2+4\equiv\{4,5\}\equiv\{1,2\}\pmod3\implies n^2+4\not\equiv0\pmod3$$ $$\therefore\quad 3\not\mid n^2+4~\forall~n\in\Bbb{Z}$$


7

Another approach we see that $n(n-1)(n+1)$ divides both $n^7-n^3=n^3(n-1)(n+1)(n^2+1)$ and $n^{21}-n^{13}=n^{13}(n-1)(n+1)(n^2+1)(n^4+1)$ and we know that $(n-1)n(n+1)$ is a multiple of $3$ because the product of three consecutive integers is divisible by $3$.


7

Note that $$5^2 \equiv 1 \pmod8 \implies 5^{200} = (5^2)^{100} \equiv 1^{100} \pmod8 \equiv 1 \pmod8$$ We hence have $$5^{200} = 8M + 1 \implies \dfrac{5^{200}}8 = M + \dfrac18$$ where $M \in \mathbb{Z}^+$. Hence, the fractional part is $1/8$. EDIT Another equivalent way is to write $5^{200}$ as $(4+1)^{200}$ and then use binomial theorem, i.e., $$5^{200} ...


7

$x\bmod5=x\bmod5$ $(x+6)\bmod5=(x+1)\bmod5$ $(x+12)\bmod5=(x+2)\bmod5$ $(x+18)\bmod5=(x+3)\bmod5$ $(x+24)\bmod5=(x+4)\bmod5$ so if $x\ne5$, then $5$ must divide one of the five integers, and it can't be $5$ itself, whence it must be composite.


7

Hint: Compute $n^2\bmod 5$ for $n=0,1,2,3,4$.


6

A monic polynomial is any polynomial $f(x)=a_n x^n + a_{n-1} + \cdots + a_1 x^1 + a_0 x^0$ such that $a_n=1$. Therefore, a monic polynomial of degree zero is of the form $f(x) = a_0$ where $a_n = a_0 = 1$ as $n=0$ so they may only take the form $f(x) = 1$.


5

Look at the expression mod $3$, $$n^2 + 4 \equiv n^2 + 1.$$ Could $n^2\equiv 2$? What are the squares mod $3$? $0^2 \equiv 0, 1^2 \equiv 1, 2^2 \equiv 4 \equiv 1$. Thus $2$ isn't a square mod $3$!


5

Let $\, \upsilon_p(n)\, $ denote $\, m\, $ s.t. $\, p^m\mid n\, $ and $\, p^{m+1}\nmid n$. LTE (Lifting The Exponent Lemma): $a,b$ odd, $n$ even$\ \Rightarrow\,\, \upsilon_2(a^n-b^n)=\upsilon_2(a-b)+\upsilon_2(a+b)+\upsilon_2(n)-1$ $7,1$ are odd, $2048$ is even, so ...


4

If $14x+13y=1$ then multiplying by $7$ gives $14(7x)+13(7y)=7.$


4

If $\,f_n = a f_{n-1} + f_{n-2}\,$ then induction shows $\,(f_n,f_{n-1}) = (f_1,f_0)$ since $\, (f_n,f_{n-1}) = (a f_{n-1} + f_{n-2},f_{n-1}) = (f_{n-2},f_{n-1}) = (f_1,f_0)\,$ by induction Remark $\ $ Similarly one can prove much more generally that the Fibonacci numbers $\,f_n\:$ comprise a strong divisibility sequence: $\,(f_m,f_n) = f_{(m,n)},\:$ i.e. ...


4

${\rm mod}\ 5\!:\,\ \color{#c00}n^2(\color{#0a0}{n^4-1})\equiv 0\, $ by $\,\color{#c00}{n\equiv 0}\,$ or $\,\color{#0a0}{n^4\equiv 1}\,$ by little Fermat. Or, directly $\,\color{#c00}{n\equiv 0}\ $ or $\ n\equiv \pm1,\pm2\,\Rightarrow\, n^2\equiv \pm1\,\Rightarrow\, \color{#0a0}{n^4\equiv 1}$


4

Notice that $(n^2 - 1)(n^2 + 1) = n^4 - 1$. Fermat's little theorem tells us that $n^4 \equiv 1 \pmod 5$. This means that $n^4 - 1$ is a multiple of $5$ if $n$ is not, and therefore $n^2 (n^4 - 1)$ is also a multiple of $5$. For example, if $n = 2$, then $n^4 - 1 = 15$ and $n^2 (n^2 - 1)(n^2 + 1) = 60$. This leaves us the case where $n$ is a multiple of $5$ ...


4

$5^n\equiv 1,5,4,-1,2,3,1\pmod{\! 7}$ for $n=0,1,2,3,4,5,6$, respectively. This pattern continues and $\, 5^n\equiv -1\iff n\equiv 3\, $ mod $6$. More rigorously: $3$ is the least nonnegative $c$ giving $5^c\equiv -1\pmod{\! 7}$. Let $n=3+k$ with $k\ge 0$. We'll show $5^n\equiv -1\pmod{\! 7}$ iff $k=6m$ for some $m\ge 0$. $5^{n}\equiv ...


3

$n^2(n^2+1)(n^2-1)=n^2(n^4-1)$ and $n^4\equiv1\mod5$ by FLT for $n\in\{1,2,3,4\}$ Or, as FLT also states that $a^{p-1+k}\equiv a^k \mod p$, and as the equation is $n^6-n^2$, the fact is immediate.


3

Your hunch is correct; you have discovered a theorem! The easiest way to explain it is by using modular arithmetic, where the integer number line wraps around a circle. Two numbers are congruent modulo $n$, written $$ a \equiv b \pmod{n} $$ if they give the same remainder upon division by $n$. Equivalently, $a \equiv b \pmod{n}$ if $n$ divides $a - b$. ...


3

Multiplying by -1 doesn't change anything. If we have 18, which we know is divisible by 9, we just multiply it by -1 to get -18 and then we do the same to how many times 9 goes into 18 to get -2, and see that 9 goes into -18 -2 times, -2 is an integer so the rule holds up.


3

We seek solutions to the Diophantine equation: $$4^x + 4^y + 4^z = k^2$$ where $x, y, z$ and $k$ are integers. Let us assume that $x$ is the smallest of the set ($x, y, z$). Dividing both sides of the equation by $4^x$ (which is a perfect square) and rearranging terms yields: $$4^u + 4^v = m^2 -1 = (m - 1)(m + 1)$$ Now the LHS is odd, only if $u = 0$ and ...


3

Sometimes it is useful in complex analysis to consider the complex numbers plus the "point at infinity". See this wiki article for details: Riemann Sphere


3

Let $m,n\in\Bbb Z$. We wish to show that $\langle m\rangle\subset\langle n\rangle$ if and only if $n\mid m$. First, suppose that $\langle m\rangle\subset\langle n\rangle$. Since $m\in\langle m\rangle$ it follows that $m\in\langle n\rangle$. That is, there exists a $k\in\Bbb Z$ such that $nk=m$. Hence $n\mid m$. Conversely, suppose that $n\mid m$. To show ...


3

Hints: There are a total of $\lfloor\frac{n}{k}\rfloor$ numbers divisible by $k$ in the set of numbers $\{1,2,\dots,n\}$ The principle of inclusion-exclusion states as a special case that $|A\cup B\cup C| = |A|+|B|+|C|-|A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|$. Let $A=\{\text{numbers in 1,2,...,5000 divisible by}~3\}$, $B=\{\text{numbers in ...


3

Let $A$ and $B$ be domains with $A\subseteq B$. We say that the ring extension $B/A$ is good if the following implication holds: $$\text{For every}\ f\in A\setminus\{0\}\ \text{and}\ h\in B,\ \text{if}\ fh\in A\ \text{then}\ h\in A\,.$$ We claim that if $B/A$ is good then $B[x]/A[x]$ is good as well. In fact, let $f\in A[x]\setminus\{0\}$ and $h\in ...


3

Consider cases. For example, what happens if $n=3k$, $n=3k+1$, and $n=3k+2$?


3

Consider the sequence $a_1, a_1+a_2, a_1+a_2+a_3, \dotsc$. There are $n$ terms in this sequence. If any one of them is divisible by $n$, then we are done. If no sum is divisible, then the $n$ sums have $n-1$ possible remainders when divided by $n$. Thus two sums must have the same remainder, and their difference must be divisible by $n$. But their ...


3

If $\frac{k^2+m^2}{2(k-m)}$ is an integer, we need $k\equiv m \pmod{2}$, or the numerator would be odd. Then $$\frac{k^2+m^2}{2(k-m)} = \frac{k^2-m^2}{2(k-m)} + \frac{2m^2}{2(k-m)} = \frac{k+m}{2} + \frac{m^2}{k-m}$$ is an integer if and only if $\frac{m^2}{k-m}\in\mathbb{Z}$. Let $d \equiv m \pmod{2}$ a divisor of $m^2$, and set $k = m+d$.



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