Tag Info

Hot answers tagged

12

Hint: Apply the rational root theorem to $$ x^2 - ( a + b) x + ab $$


12

If $d|a$, then $a = dn$ for some integer $n$. If $d|b$, then $b = dm$ for some integer $m$. Multiply $a$ and $b$ together: $ab = (dn)(dm) = d^2mn$ which is exactly what $d^2|ab$ means.


11

Modest progress. There are infinitely many integers $n$ such that $n^3+1\mid n!$. We always have $n^3+1=(n+1)(n^2-n+1)$. Let $n=k^2+1$. Then $$ n^2-n+1=(1+k+k^2)(1-k+k^2). $$ Assume further that $k\equiv1\pmod3$. In that case $1+k+k^2$ and $n+1=2+k^2$ are both divisible by $3$. For all sufficiently large $k\equiv1\pmod3$ we thus have $$ ...


11

Using modular arithmetic: If $x \equiv 0 \mod 4$, then $x^3 \equiv 0 \mod 4$ and $x^3-2 \equiv 2 \mod 4$. If $x \equiv 1 \mod 4$, then $x^3 \equiv 1 \mod 4$ and $x^3-2 \equiv 3 \mod 4$. If $x \equiv 2 \mod 4$, then $x^3 \equiv 8 \equiv 0 \mod 4$ and $x^3-2 \equiv 2 \mod 4$. If $x \equiv 3 \mod 4$, then $x^3 \equiv 27 \equiv 3 \mod 4$ and $x^3-2 \equiv ...


8

It suffices to show that for infinitely many $n$, the largest prime factor of $n^{2015}+1$ is at most $\sqrt{n}$. Indeed, if $n$ is such a large integer and $p$ is a prime, then the largest value of $a$ for which $p^a\mid n^{2015}+1$ is $\leq c \log n$ for some constant $c$, while $n!$ is divisible by $p^a$ with $a\geq \frac{n}{p}-1\geq \sqrt{n}-1>c \log ...


7

HINT: If $n\equiv0,\pm1,\pm2,\pm3;n^2\equiv0,1,4,2\pmod7$ So, $a^2,b^2\equiv1,2,4$ Check for $c^2\pmod7$ when $a^2\not\equiv b^2\pmod7$ But my greater concern is how the problem, specifically $\pmod7$ was conceived!


7

The answer is yes, because $4^2\equiv 4\pmod{6}$, and hence $4^n\equiv 4\pmod{6}$ for all $n\ge 1$.


6

$n^3+3n^2+2n=(n+1)(n+2)n$. One of the factors must be even and one must be a multiple of three. Hence the product is a multiple of both $2$ and $3$ and hence is divisible by the least common multiple of $2$ and $3$, which turns out to be $6$.


5

Using Euclid's formula, $a=2mn, b=m^2-n^2$ We have $7\nmid2mn(m^2-n^2)$ Now, $(m^2-n^2)^2-(2mn)^2=m^4+n^4-6m^2n^2\equiv m^4+n^4+m^2n^2\pmod7$ But $(m^2-n^2)(m^4+n^4+m^2n^2)=(m^2)^3-(n^2)^3\equiv1-1\pmod7$ using Fermat's Little Theorem as $(m,7)=(n,7)=1$ $\implies7|(m^4+n^4+m^2n^2)$ as $7\nmid(m^2-n^2)$ Can you take it from here?


5

In problem (a), use Fermat's little theorem, which says (or a rather, a very slightly different version says) that for any prime number $p$, and any integer $n$ that's not divisible by $p$, we have $$n^{p-1}\equiv 1\bmod p$$ In particular, use $n=2$ and $p=17$. Keep in mind that $2017=(126\times 16)+1$. In problem (b), note that $30\equiv 61\equiv -1\bmod ...


5

Hints: a) $2016$ is divisible by $16$. Now use Fermat's Theorem. b) $30\equiv -1\pmod{31}$ and $61\equiv -1\pmod{31}$. c) If the prime $p$ is not equal to $3$ then $p^2\equiv 1\pmod{3}$.


5

Let’s look at the non-negative integers having base ten representations requiring at most $d$ digits. (Including $0$ makes no different in the limit and makes the calculation simpler.) There are $10^d$ of them. Of those, $9^d$ have representations without a $7$. Thus, the fraction of these numbers with a $7$ in their representations is ...


4

Let $p^4-20p^2+19 = (p^2-1)(p^2-19)$, and $180 = 6^2\cdot 5$. But $p\equiv \pm 1\pmod{6}$, so $p^2\equiv 1\pmod{6}$, thus $p^2-1 \equiv 1-1 = 0 \pmod{6}$ and $p^2-19 \equiv 1-19 = -18 \equiv 0 \pmod{6}$, therefore $6^2 \mid p^4-20p^2+19$. On the other hand $p\not \equiv 0\pmod{5}$, so $p^2\equiv \pm 1\pmod{5}$ and $p^4\equiv 1\pmod{5}$, thus $p^4-20p^2 + 19 ...


4

Since $2015 = 5\cdot 13\cdot 31 $, and $n^a + 1| n^{ab}+1 $ if $b$ is odd, a necessary condition for $n^{2015}+1 | n! $ is $n^m+1 | n!$ for every $m$ in $\{5, 13, 31 , 5\cdot 13 , 5\cdot 31 , 13\cdot 31 \} $. Solutions are going to be hard to find. All those expressions of the form $n^j-n^{j-1}+...-n+1 $ for odd $j$ will have to have all prime factors $\le ...


4

Let $n:=a+b$ and $m:=ab.$ Then $a^2-an+m=0$ and hence $$a=\dfrac{n\pm\sqrt{n^2-4m}}{2}.$$ note that since $a\in\Bbb Q,$ then $n^2-4m$ must be a perfect square. Then necessarily $2\mid n\pm\sqrt{n^2-4m}$ (if $n$ is odd, then $n^2-4m$ is odd $\Longrightarrow$ $n\pm\sqrt{n^2-4m}$ is even; if $n$ is even, then $n^2-4m$ is even $\Longrightarrow$ ...


3

For all $n$, $$ 4^n\equiv1^n\equiv1\pmod{3} $$ For all $n\gt0$, $$ 4^n\equiv0^n\equiv0\pmod{2} $$ Therefore, by the Chinese Remainder Theorem $$ 4^n\equiv4\pmod{6} $$ and therefore, for all $n\gt0,$ $$ 4^n+2\equiv0\pmod{6} $$


3

$$x^3\equiv2\pmod4\implies x^3\equiv2\pmod2\equiv0$$ as $x^3-x=x(x-1)(x+1)\equiv0\pmod2, x^3\equiv x\pmod2$ $\implies x$ is even $\implies x^3\equiv0\pmod4$


3

If $k$ is odd $x^3$ is odd and $x^3-2$ also, so $4$ can't divide it. If $x$ is even it is $2k$ and so $x^3-2=(2k)^3-2=8k^3-2=4(2k^3)-2$ and so it is not a multiple of $4$


3

A) \begin{align*} &\,(2a+1)^2+(2b+1)^2=(4a^2+4a+1)+(4b^2+4b+1)=4(a^2+b^2)+4(a+b)+2\\ =&\,2[2(a^2+b^2)+2(a+b)+1]. \end{align*} Since $2(a^2+b^2)$ and $2(a+b)$ are both even, the expression between the brackets is odd because of the $+1$ term. Now, the double of an odd number can never be a perfect square. (Try proving this last statement.) B) ...


3

Hint For part A), it may be helpful to first prove the following: $n^2 \equiv 0~\text{or}~1\mod{4}$ for all integers $n$.


3

Let $d = \gcd(a, b)$, and let $a = dA$ and $b = dB$. Then, since $\operatorname{lcm}(a, b) =\frac{ab}{\gcd(a, b)} =\frac{ABd^2}{d} =ABd $, $d+ABd =Ad+Bd $, so $1+AB =A+B $ or $0 =AB-A-B+1 =(A-1)(B-1) $. Therefore either $A=1$ or $B=1$. If $A=1$, then $a = dA = d$ divides $b = dB$. Similarly, if $B = 1$, $b$ divides $a$.


3

$180=5\cdot9\cdot4$ For any integer $p, p^4-20p^2+19\equiv p^4-2p^2+1\pmod9$ Now $p^4-2p^2+1=(p^2-1)^2$ For $(p,3)=1,p\equiv\pm1\pmod3\implies p^2\equiv1\pmod3\iff p^2-1\equiv0$ and for any integer $p, p^4-20p^2+19\equiv p^4-1\pmod{20}$ $\implies p^4\equiv1\pmod5$ by Fermat's Little Theorem for $(5,p)=1$ Now if $(p,2)=1$ $p\pm 1$ are even,$\implies ...


3

Just write every term in the sum in terms of $a_1$ and $a_2$ (keeping in mind that $a_{n+2}=a_n+a_{n+1}$): $$a_1+a_2+(a_1+a_2)+(a_1 + 2a_2)+(2a_1+3a_2)+(3a_1+5a_2)+(5a_1+8a_2)+(8a_1+13a_2)+(13a_1+21a_2)+(21a_1+34a_2). $$ Then the sum is clearly equal to $55a_1+88a_2 = 11(5a_1+8a_2)$, which is $11$ times the seventh term of the sum.


2

Take a common divisor $k$ of $a$ and $b$. That means that we can write $a=ka'$, $b=kb'$. Then, if $d=ax+by$, $$d=a'kx+b'ky=k(a'x+b'y)$$ so we see that $k$ also divides $d$. Since $\gcd(a,b)$ is a common divisor of $a$ and $b$ (namely, the greatest), it also holds the property. Actually, the idea behind this is very simple: the sum of two multiples of the ...


2

I dont understand programming, but what I can tell you is $\frac{a+b}{c+d} \neq \frac{\frac{a}{b}+\frac{c}{d}}{2}$, that is why it didn't work. What you can do is may be, try $\frac{a+b}{c+d}=\frac{\frac{a}{b}+1}{\frac{c}{d}+1}.\frac{b}{d}$. In you example $a=12,b=6,c=5,d=2$ which will give you $2.57$


2

$$(a^2+3)(a^2+7)=(a^2-1+4)(a^2-1+8)=\{(a-1)(a+1)\}^2+12(a-1)(a+1)+32$$ Now as $a$ is odd, one of $a-1,a+1$ is divisible by $4$ and the other is by $2,$ not by $4$ $\implies 4\cdot2$ divides $(a-1)(a+1)$


2

In fact, it does not work for all $k, x \in \mathbb{Z}$. Consider $k = 4, x = 2$: $4$ does not divide $2^4 - 2 = 16 - 2 = 14$. However, this works if $k$ is prime, and is well-known Fermat's little theorem.


2

In $\mathbf Z/4\mathbf Z$, the squares are $0$ and $1$, hence the cubes are $0,1,-1$, not $2$.


2

First remember the obvious fact that $4 = 2 \times 2$, then everything else falls into place. If $x = 2y$ (meaning that $x$ is even), then $x^3 = (2y)^3 = 8y^3$. Then $$\frac{x^3 - 2}{4} = \frac{8y^3 - 2}{4} = 2y^3 - \frac{1}{2},$$ which is clearly not an integer. If $x$ is odd, I'm not telling you anything new with that $x^3$ is odd also, as well as $x^3 ...


2

As you point out, a 7-digit number cannot have a 5 in it (otherwise, it would have to end in 5, but would have to have one of 2, 4, 6, or 8 in it, so must be even). Thus a 7-digit number $x$ contains 7 of 1, 2, 3, 4, 6, 7, 8, 9. We need only identify the missing digit. If it is not 9, the resulting number must be divisible by 9, so the missing digit must be ...



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