Tag Info

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 HINT : In mod 7,$$a^2\equiv 0,1,2,4.$$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