# Tag Info

15

You can prove it directly: notice that \begin{align}n^3 + 5n &\equiv n^3-n \pmod 6 \\&= (n-1)(n)(n+1) \pmod 6\end{align} Now, at least one of $n-1,n,n+1$ must be divisible by 2. The same argument goes for 3. Hence both $2$ and $3$ must divide $n^3+5n$. Hence $6= 2\cdot3$ must divide $n^3+5n$.

14

I'll use $\big(a,b\big)$ to denote the gcd of $a$ and $b$. The basic idea of division algorithm is that $(a,b) = (a - kb,b)$ for any integer $k$. \begin{align*} \Big((n+1)! + 1 \; , \; n! + 1\Big) &= \Big([(n+1)! + 1] - (n+1)[n! + 1] \; , \; n! + 1 \Big) \\ &= \Big((n+1)(n!) - (n+1)(n!) + 1 - (n+1) \; , \; n! + 1 \Big) \\ &= \Big(-n , \; n! + 1 ...

12

Division by zero is undefined. So $\dfrac 10$ does not exist. You are mixing up limits with numbers. That is, we can meaningfully speak of $\lim_{x \to 0} \dfrac 1x$, but $$\lim_{x \to 0^+} \frac 1x \neq \frac 10$$

9

Since $n$ is even, we can write $n = 2k$ for some integer $k$. Hint: $$n(n^2 + 20) = 2k((2k)^2 + 20)= 2k(4k^2 + 20) = 8k(k^2 + 5)$$ Hence, $8$ is a factor. Note further that one of $k$ or $k^2 + 5$ must be even, and hence divisible by $2$. Why? So now we know that $8\cdot 2 = 16$ is a factor. All that remains to be shown is that $3$ is also a factor.

6

This is a classical consequence of the Chinese remainder theorem. Denote by $p_1,p_2,\ldots,p_r$ the prime divisors of $b$. For each $i$, $p_i$ does not divide both $a$ and $N$. I claim that there is a $x_i\in{\mathbb Z}$ such that $a+Nx_i$ is not divisible by $p_i$. Indeed, if $p_i$ divides $N$ then it does not divide $a$ by the above so any $x_i$ will ...

6

Every odd prime has this property - even if you replace $p^2$ by $p^k$. (pretty awesome, huh) Find a solution $(x_1,y_1)$ to $x_1^2+y_1^2+1\equiv0\pmod p$; without loss of generality, $p$ doesn't divide $x_1$. Consider the polynomial $x^2+(y_1^2+1)$. This polynomial has a root $x_0$ modulo $p$, and its derivative at that root is $2x_0\not\equiv0\pmod p$. ...

5

If we set $$S(n) = \sum_{k=0}^{2^n-1} (-1)^{a(k)}\cdot 2^k,$$ then we note that $a(2^n + k) = a(k) + 1$, and hence $$S(n+1) = \sum_{k=0}^{2^{n+1}-1} (-1)^{a(k)}\cdot 2^k = \sum_{k=0}^{2^n-1} (-1)^{a(k)}\cdot \left(2^k - 2^{2^n+k}\right) = -\left(2^{2^n}-1\right)\cdot S(n).$$ Thus $$\lvert S(n)\rvert = \prod_{k=0}^{n-1} \left(2^{2^k}-1\right).$$ Now ...

5

There is undoubtedly a nicer answer, but here goes. Note that $3\cdot 2+(-1)\cdot 5=1$. Because it looks nicer, let $a=3$ and $b=-1$. Consider $(2a+5b)^{2n-1}$, and expand using the Binomial Theorem. Then the first $n$ terms will be divisible by $2^n$, and the last $n$ will be divisible by $5^n$. That gives us the desired linear combination. Explicitly, ...

5

The key identity is $$\gcd (a,b) = \gcd (a-kb ,b).$$ So, the task is to choose the $k$ such that the expression gets simpler. In this particular case, it is the plus 1 which is blocking the nice multiplicative structure, so you can choose $k=1$ to eliminate it which gives $$\gcd ((n+1)!+1,n!+1) = \gcd (n\cdot n! ,n!+1).$$ But this is clearly 1 because ...

4

$2^n/3=2\cdot2\cdot\ldots\cdot2/3$. Proof by induction: Let $n=1$. $2/3$ is just $0$ with remainder $2$. Hence, there exists a remainder for $2/3$. How about $2^{n+1}/3$? Using the previous proof that $2/3$ has a remainder, and expanding $2^{n+1}/3$ as $2^n\left(2/3\right)$ shows that $2^{n+1}/3$ has a remainder. Therefore, $\forall n, 2^n/3$ has a ...

4

If such $a,b,c,d$ existed, the fact that $(a,b,c)$ is a Pythagorean triple yields integers $u,v$ such that $a=u^2-v^2,b=2uv$ (say). Putting $g={\sf gcd}(u,v)$ and $x=\frac{u}{g},y=\frac{v}{g}$, we have $a=g^2(x^2-y^2),b=2g^2xy$, so that $2g^4xy(x^2-y^2)=ab=2d^2$. Then $d'=\frac{d}{g^2}$ is an integer and $$xy(x-y)(x+y)=(d')^2 \tag{1}$$ Since $x$ and $y$ ...

4

Since this is a graduate level number theory class, I think it's safe to assume that you are familiar with modulo arithmetic? Given any list of $n$ consecutive integers, $a, a+1, a+2, \dots, a+n-1$, modulo $n$ this list is equivalent to $0,1,2,3,\dots,n-1$ modulo $n$. (Note that I am not saying $a \equiv 0 \pmod{n}$). This list can be rewritten as: $1 ... 4 For both problems, you should use the following corollary of Euler's theorem: if$\gcd(a,q)=1$and$j\equiv k\pmod{\phi(q)}$, then$a^j\equiv a^k\pmod q$. For example, finding the last five digits of$5^{5^{5^5}}$is equivalent to calculating the least positive residue of$5^{5^{5^5}}\pmod{10^5}$. But by the corollary, you only need to know$5^{5^5}$modulo ... 3 Proof: Base case:$n=1$:$((1)^3 + 5(1)) = 6$which is divisible by 6. Inductive step: Suppose that$(n^3 + 5n)$is divisible by$6$, prove that$((n+1)^3 + 5(n+1))$is divisible by 6. Therefore:$((n+1)^3 + 5(n+1))$=$(n^3 + 3n^2 + 3n + 1) +(5n + 5)$$$=(n^3 + 5n) + 3(n^2 + n) + 6$$ Do you think you can take it from here? 3 I admit that this question troubled me also as a kid.. But I found this explanation satisfactory: Saying$c=\dfrac {a}{b}$means calculating the number of chocolates each donkey will receive if$a$chocolates are divided among$b$donkeys. But, if the number of donkeys itself is zero, we cannot divide the$a$chocolates in any definite way, or the question ... 3 Note that if$5|n$then the answer is$0$If$n\equiv 1 \mod 5$then the remainder will always be$1$If$n\equiv -1 \mod 5$then the remainder will be$1$or$4$dependent on whether$n$is even or odd (note:$-1$has order$2$in the multiplicative group of non-zero residues, and the answer therefore depends on$n \mod 2$). If$n\equiv 2,3 \mod 5$- ... 3 A number is divisible by$ 8 $if the last three digits are divisible by$ 8$. Now, we can arrange the first$5$digits of our answer in$ 5^5 $ways, because each of the position can take$ 1$of$5$values. Now, our problem reduces to the following. How many three digit numbers formed with$\{1,2,3,4,5\}$are divisible by$8$? We can enumerate all the ... 3 Hint: As$7^4=2401$the numbers$a$have at most four digits in base$7$, three of which must be equal. The divisibility test for$11$in base$10$(add up the even places and subtract the odd places) is actually a test for$b+1$in base$b$, so will give you an easy check for divisibility by$8$. There not many numbers to check. 3 In base 7 a number is divisible by 8 if and only if the alternating sum of its digits is divisible by 7. If 3 digits are equal, and the alternating sum is divisible by 7, the 4th digit must also be equal. Therefore, the answers are 0000, 1111, 2222, 3333, 4444, 5555, and 6666 (all written in base 7). (I am not sure if you would characterize 0000 as having ... 3 According to the Fundamental theorem of arithmetic, every integer greater than$1$has a unique prime factorization. Since$2$and$3$are prime,$2^n$($n>0$) is already the prime factorization, and does not have$3$as a factor. Hence it is not divisible by$3$. 3 The question is indeed equivalent to find solutions for an 1-cycle in the Collatz-problem. Let's first rewrite your divisibility - criterion as a cofactored expression $$2^n-1 = (2^{n+m}-3^m) \cdot h \qquad \qquad \text{for some integer h \ge 1 }\tag 1$$ From the study of cycles in the Collatz-problem there is the theorem:$ \qquad \qquad$There ... 3 The question is equivalent to proving that, for any integer$m$,$6$divides$m(m^2+5)$, because for$n=2m$the expression is$8m(m^2+5)$. Divisibility of$m(m^2+5)$by$2$is obvious, because$m^2\equiv m\pmod{2}$, so $$m(m^2+5)\equiv m(m+1)\equiv m^2+m\equiv 2m\equiv 0\pmod{2}.$$ Divisibility of$m(m^2+5)$by$3$follows similarly, because$m^3\equiv ...

3

First $$3(x^3+1)-(3x^2+3x+1)(x-1)=2x+4$$ and $$2(3x^2+3x+1)-3(2x+4)(x-1)=14$$ Thus, we have $$(3x^2-6x+5)(3x^2+3x+1)-9(x-1)(x^3+1)=14$$ and thus, $(x^3+1,3x^2+3x+1)\mid14$. Since $3x^2+3x+1=6\binom{x+1}{2}+1$, it is always odd. Thus, we can improve the statement to $$(x^3+1,3x^2+3x+1)\mid7$$ If we look mod $7$, we see that the gcd is $7$ when ...

3

By the Fundamental Theorem of Arithmetic every integer is the product of a unique set of primes. That is $n = q_1q_2..q_p$. But since $n$ contains no square factors each prime factor is distinct. Now $n \ | \ a^2 \implies q_j \ | \ a^2$. By Euclid's Lemma $q_j \ | \ a$. And this is true for all $j = 1, 2, .. p$. Again, since the $q_j$'s are distinct primes ...

2

With your procedure you found that the GCD between the two polynomials $x^3+1$ and $3x^2+3x+1$ in $\mathbb{Q}[x]$ is $7$, or equivalently $1$, because the GCD of polynomials is defined up to constants (every scalar value $c$ divides any polynomial $p(x)\in\mathbb{Q}[x]$). Thus there is not contradiction in your statement.

2

It can be finished your way: $\ 3^n(3+1+\overbrace{1/3}^{\large \color{#c00}{-4}}) \,\equiv\, 0,\$ by $\ \dfrac{1}3\equiv \dfrac{-12}{\ 3}\equiv \color{#c00}{-4}\pmod{13}$ But here there is no need to use fractions, since we can proceed fraction-free as in Dror's answer. Furthermore, one needs to be very careful with fractions in modular arithmetic lest ...

2

Let $n = 2k$ for some integer $k$. Then, \begin{align}2k((2k^2) + 20) &= 2k(4k^2 + 20)\\ &=8k(k^2 + 5)\end{align} But \begin{align}k(k^2 + 5) &\equiv k(k^2-1)\mod 2\\ &=(k+1)(k)(k-1) \mod 2\end{align} Since $2$ must divide at least one of these three consecutive integers, we have $2 \mid k(k^2 + 5) \implies 16 \mid 8k(k^2 + 5)$. ...

2

${} \bmod 16$, we have $n(n^2+20) \equiv n(n^2+4)=2k(4k^2+4) = 8k(k^2+1)$. If $k$ is even then clearly $8k(k^2+1)\equiv 0$. If $k$ is odd, then $k^2+1$ is even and again $8k(k^2+1)\equiv 0$. ${} \bmod 3$, we have $n(n^2+20) \equiv n(n^2-1)=(n-1)n(n+1)\equiv 0$, since given three consecutive numbers, exactly one of them is a multiple of $3$. Therefore, $16$ ...

2

Since the indices of the factors in the strictly increasing order don't actually play any role, I'll use $A,B,P,Q$ to denote the actual factors instead of $\tau_a(n)$, $\tau_b(n)$, $\tau_p(n)$ and $\tau_q(n)$. The condition given can then be rewritten as $AB=PQ=n$ and $A+B=P-Q$. Let's start by showing that all numbers from OEIS A009112 admit such ...

2

Of all the numbers that are formed with 1,2,3,4,5 - the last three digits need to be divisible by 8. There are 5^3 ways you could arrange the five numbers for the last three digits. Of these last three digits that are divisible by 8 are 312, 152, 512, 432, 352, 112, 232, 224, 144, 424, 344, 552, 544. A total of 13 of them which I got by brute force ...

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