Tag Info

Hot answers tagged divisibility

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 04x^2+20x+64\equiv 04x^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$13we have \begin{aligned} n^2+5n+16 &\equiv n^2 + 18n + 81 \\ &= (n+9)^2 \qquad\text{ modulo }13\ . \end{aligned} Son$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 geta=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