9

This is one of my favorite elementary number theory problems. Hint: $$f(n)=n^2+5n+16=(n^2+5n-36)+52$$


6

$$ \frac {37!}{19!20!}$$ is not an integer We know that there are two $19$ in the bottom but only one in the top. Since $19$ is prime the fraction does not simplify to an integer.


6

A nice solution is given by the natural embedding of $S_n$ into $\mathrm{GL}_n(\mathbb{F}_2)$. Here $S_n$ is the symmetric group of $n$ elements. Every element of $S_n$ permutes the canonical basis of $\mathbb{F}_2^n$, hence gives an $\mathbb{F}_2$-linear automorphism of $\mathbb{F}_2^n$. This embeds $S_n$ as a subgroup of $\mathrm{GL}_n(\mathbb{F}_2)$. ...


5

Hint For each odd prime $p$, if $p^k |m \leq n$ then $$p^k |2^{\frac{p-1}{p}m}-1$$ and hence $$p^k| 2^{n}-2^{n-\frac{p-1}{p}m}$$


5

If $b^2 + ba + 1$ divides $a^2 + ab+1$, then it also divides $(a^2+ab+1)-(b^2+ba+1) = a^2-b^2$, which factors as $(a+b)(a-b)$. However, it can't share any divisors with the first factor: $\gcd(b^2+ba+1, a+b) = \gcd(b^2+ba+1 - b(a+b), a+b) = \gcd(1, a+b) = 1$. Therefore $b^2+ba+1$ also divides $\frac{a^2-b^2}{a+b} = a-b$. However, $b^2+ba+1 > a > a-b$...


5

Suppose it is, then also $$13\mid n^2+5n+16$$ so $$13\mid (n^2+5n+16)-13n=n^2-8n+16$$ so $$ 13\mid n-4\implies 169\mid (n-4)^2 = n^2-8n+16$$ So $$169 \mid (n^2+5n+16)-(n^2-8n+16)= 13n\implies 13\mid n$$ But then from 1.st relation we get $$13\mid 16$$ a contradiction!


3

If $b^2+ba+1$ divides $a^2+ab+1$ then $b^2+ba+1 \le a^2+ab+1$ and so $b \le a$. Suppose $b<a$. Then $b^2+ba+1$ divides the difference $(a^2+ab+1) - (b^2+ba+1) = a^2-b^2$. But $b^2+ba+1 = b(a+b)+1 = 1 \mod a+b$ and $a^2-b^2=(a-b)(a+b) = 0 \mod a+b$. So either $a+b=1$, in which case $b=0, a=1$; or $b \not \lt a$ in which case $a=b$.


3

Suppose $p$ is prime. If $p$ divides $2n^7+1$ & $3n^3+2$ then $p$ divides $2(2n^7+1)-(3n^3+2)=n^3(4n^4-3)$ then $p$ divides $4n^4-3$ ( See Footnote ) then $p$ divides $2(4n^4-3)+3(3n^3+2)= n^3(8n+9)$ then $p$ divides $8n+9$ (See Footnote) then $p$ divides $9(3n^3+2)-2(8n+9)=n(27n^2-16)$ then $p$ divides $27n^2-16$ (See Footnote) then $p$ divides ...


3

I have a solution, but I'm sure there's a better way to do this. The greatest common divisor $g$ of of $2n^7+1$ and $3n^3+2$ must also divide $$3(2n^7+1)-2n^4(3n^3+2)=3-4n^4$$ then $g$ must also divide $$4n(3n^3+2)-3(4n^4-3)=8n+9$$ Then $g$ must divide $$ 3n^4(8n+9)-8(3n^3+2)=27n^2-16$$ Continuing in this manner, we eventually find that $g$ must divide $...


2

Let $d = \gcd(2n^7+1, 3n^3+2)$. Then since $2n^7+1 \ | \ 2^3n^{21}+1$ and $3n^3 + 2 \ | \ 3^7n^{21}+2^7$, we must have $$d \ | \ 3^7(2^3n^{21}+1) - 2^3(3^7n^{21}+2^7) \quad\Rightarrow\quad d \ | \ 1163.$$ Since $1163$ is a prime, if the fraction is reducible, $1163 \ | \ 3n^3 + 2$. Since $1163 \equiv 2 \pmod 3$, $n^3 \equiv -2\cdot 3^{-1} \equiv 587 \pmod{...


2

Let us prove that for every $\varepsilon > 0$ there exist infinitely many integers $n > 0$ such that $P(n^2 + 1) < \varepsilon n$. Obviously, it is enough to prove that there exists one such $n$. As you noticed, if $n = 2m^2$, for some integer $m > 0$, then $n^2 + 1 = (2m^2 - 2m + 1)(2m^2 + 2m + 1)$. Hence, it is enough to prove that we can ...


2

This gcd can be computed purely mechanically by a slight generalization of the Euclidean algorithm which allows us to scale by integers $\,c\,$ coprime to the gcd during the modular reduction step, i.e. $$(a,b)\, = \,(a,\,cb\bmod a)\ \ \ {\rm if}\ \ \ (a,c) = 1\qquad\qquad\ \, $$ which is true since $\,(a,c)= 1\,\Rightarrow\, (a,\,cb\bmod a) = (a,\,b\bmod ...


2

Hint: Term $n-1$ in $S_2$ has the value $n$. If term $n-1$ in $S_n$ still has the value $n$ then this means this value $n$ was not changed at any point during the construction of $S_3, S_4, \dots S_n$ (because once a value in the sequence is changed, it can only increase - it can never go back to its original value). But if $n$ was divisible by some $m$ in ...


2

Hint: You're almost there. Since $101$ is a prime number, it will divide $\ \frac{(3n+2)!}{14!(3n-12)!}\ $ evenly if and only if it divides one of the numbers $\ 3n+2,3n+1, 3n, \dots,3n-11\ $.


1

Let's try to complete the square. Equivalences below are $\bmod 169$. $x^2+5x+16\equiv 0$ $4x^2+20x+64\equiv 0$ $4x^2+20x+25=(2x+5)^2\equiv 25-64=-39$ We need to find a quantity whose square is $\equiv -39$. Unfortunately this is a multiple of $13$ and the only square multiples of $13$ are also multiples of $169$ --therefore $\equiv 0\not\equiv -39$. ...


1

Let $n\in \Bbb Z$ be so that $n^2+5n+16$ is divisible by $13$. Then working modulo $13$ we have $$ \begin{aligned} n^2+5n+16 &\equiv n^2 + 18n + 81 \\ &= (n+9)^2 \qquad\text{ modulo }13\ . \end{aligned} $$ So $n$ is of the form $n=4+13k$, we substitute and get (computation in $\Bbb Z$): $$ \begin{aligned} n^2+5n+16 &= (13k +4)^2 + 5(13k+4) + 16 \\...


1

I can't comment (not enough reputation). You did a good job, and you indeed proved that $S_{x,y}\subset \{n\in\mathbb N : d\mid n\}$.


1

Suppose $4a=7k$ for some $k$. Use Bézout's identity: we have $1=2\cdot 4- 7$, so, multiplying both sides by $a$, we get $$a=2\cdot 4a-7a=7(2k-a).$$


1

Since $7\mid 4a$, then we can write, that $7\mid 21a - 5 \times 4a$, because both $21$ and $4a$ are divisible by $7$, which leads to $7\mid a$.


1

The extended euclidean algorithm for gcd (of polynomials with rational coefficients) also tells us that $$ \left( 2 x^{7} + 1 \right) \left( { 1728 x^{2} - 1944 x + 2187 } \right) - \left( 3 x^{3} + 2 \right) \left( { 1152 x^{6} - 1296 x^{5} + 1458 x^{4} - 768 x^{3} + 864 x^{2} - 972 x + 512 } \right) = 1163 $$ =-=-=-=-=-=-=-=-=-=-=...


1

I don't see how your observation of the divisors of powers of primes can be applied here. The question says $a,b,c,d$ are relatively prime, which means no $2$ of them have any factor in common, but none of them are necessarily prime and, in fact, one or more may be $1$, not to mention possibly being composite numbers. Instead, first note $a,b,c,d$ are each ...


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