Tag Info

Hot answers tagged

10

If you have 10 cookies and each kid gets 2 cookies, how many kids can you serve? It's $10\div 2 =5$ kids. If you have 10 cookies and each kid gets 2.5 cookies, how many kids can you serve? It's $10\div 2.5 =4$ kids. If you have 1 cookie and each kid gets 0.5 cookies, how many kids can you serve? It's $1\div 0.5 =2$ kids.


9

The set $\,S\,$ of naturals $\,n\,$ such that $\,\color{#c00}{p\mid nb}\,$ is $\rm\overbrace{closed\ under\ subtraction}^{\overbrace{\large p\mid nb,kb\,\Rightarrow\, p\mid nb-kb\, =\, (n-k)b}^{\LARGE n,\,k\ \in\ S\ \ \ \Longrightarrow\ \ \ n-k\ \in\ S\ \ }}$ and $\, a,p\in S\,$ so by the Lemma its least positive element $\,\color{#0a0}{d\mid a,p}.\,$ Since ...


9

For what it is worth, I just timed myself doing trial division: $10001=100^2+1$, so I only need to check primes that are 1 mod 4 $10001=10010-9$, so not $7$, $11$, $13$ $10001=10030-29$, so not $17$ or $29$ $10001 = 9990+11$ so not $37$ $41*61 = 2501 = 10001-7500$ so not $41$ or $61$ $10600-10001 = 599$ so not $53$ $10001 +219 = 10220 = 20*511 = ...


6

if $n\geq 7$ and $n$ is divisible by all numbers less then $\frac{n}{2}$, so $n$ is even and we can deduce easily that $\frac{n}{2}(\frac{n}{2}-1)$ divides $n$ (because $\gcd(\frac{n}{2},(\frac{n}{2}-1))=1$) and the most important: $$\frac{n}{2}(\frac{n}{2}-1)\leq n$$ whence : $n-2=2(\frac{n}{2}-1)\leq 4$ so $n\leq 6$


5

Maybe someone was lucky enough to read List of Primes and remembered (like me) there are only two known "Generalized Fermat primes base 10", so 10001 is not prime. Does that count? P.S. You could also use this A theorem about prime divisors of generalized Fermat numbers? to find you "only" need to divide 10001 by prime numbers of the form $8k+1$ for ...


5

If $p\not\mid a$, then $\gcd (p,a)=1$ (why?). Since $p\mid ab$ and $\gcd (p,a)=1$, the Euclid's lemma implies that $p\mid b$.


5

$$a^3-a=(a-1)a(a+1)$$ which is a product of three consecutive integers. So, exactly one of them must be divisible by $3$ and at least one of them must be even. More generally The product of n consecutive integers is divisible by n! (without using the properties of binomial coefficients)


4

No induction required to prove that. Write the expression as: $$(n-1)^3+n^ 3+(n+1)^3, \quad n>0$$ instead, i. e. as: $$3n(n^2+2).$$ Now, either $n\equiv 0\mod 3$, and $3n\equiv 0\mod 9$; or $n\equiv \pm 1\mod 3$, and $n^2+2\equiv 0\mod 3$, so that $3(n^2+1)\equiv 0\mod 9$.


4

Here is one, which uses only euclidean division and the well-order on $\mathbf N$: Let $E = \bigl\{x ∈ \mathbf N^{\boldsymbol *} \mid p\enspace \text{divides}\enspace xb\}$ . $E$ is not empty, since it contains at least $p\,$ and $\,a $.Thus it contains a smallest element, $x_0$. This element divides each $x\in E$: indeed the euclidean division of $x$ by ...


4

Take $n=2k+1~,~k\geq 0$ since $n$ is odd. Now, $$2^n=2^{2k+1}=2\cdot 4^k\equiv 2\cdot (-1)^k\equiv \begin{cases}2~,~k\textrm{ is even}\\ 3~,~k\textrm{ is odd}\end{cases}\pmod{5}$$ $$2^n-1=2^{2k+1}-1\equiv\begin{cases}1~,~k\textrm{ is even}\\ 2~,~k\textrm{ is odd}\end{cases}\pmod5\implies 2^n-1\not\equiv 0\pmod{5}~\forall~\textrm{odd }n$$ $$\therefore\quad ...


4

HINT: $k$ should divides $$(26+35n)-5(3+7n)=11$$ Also if you want to find the corresponding values of $n$ solve two linear Diophantine equations $$26+35n=11a\,\,\,\,\,\,\,\,\,\ 3+7n=11b$$ simultaneously for $a, b$ and $n.$


4

The answer is yes, but just because $(a,b,c)$ is a primitive Pythagorean triple. Assume for contradiction that $\gcd(a,b)>1$. Then $\exists p\in\mathbb P(p\mid a,b\Rightarrow p\mid a^2+b^2=c^2\Rightarrow p\mid c\Rightarrow \gcd(a,b,c)\ge p)$, contradiction. If $a,b,c$ weren't a primitive Pythagorean triple, a counterexample would be ...


4

Since $d\mid(ad+b)$, there exists an integer $n$ such that $nd = (ad+b)$. So $nd-ad = b$ and thus $d(n-a) = b$. But since $n$ and $a$ are integers, it follows that $d$ divides $b$.


4

The way to express your ideas formally is to use modular arithmetic. To say that the possible remainders for $a^2$ are $0,1,2$, and $4$ is to say that $$ a^2 \equiv 0,1,2,4 \pmod 7. $$ The same is true for $b^2$, and $7|a^2 + b^2$ if and only if $a^2 + b^2 \equiv 0 \pmod 7$. But notice that if $i,j\in \{0,1,2,4\}$, then $i+j \equiv 0 \pmod 7$ if and only if ...


4

Since $n>6$, we have that $2<3 <n/2$, so $n$ is divisible by $2$ and $3$. Since $n=2\cdot\frac{n}{2}$ and $\frac{n}{2}-1<\frac{n}{2}$, $\frac{n}{2}-1$ divides $n$. $\frac{n}{2}−1$ must have the next smallest codivisor, which is $3$, so must be equal to $\frac{n}{3}$. Solving $\frac{n}{2}-1=\frac{n}{3}$ gives $n=6$, a contradiction to ...


4

We have $$(n^2+1) - (n-1)(n+1) = 2$$ Hence, if $d = \gcd(n^2+1,n+1)$, then $d$ divides $2$. Hence, $d$ has to be $1$ or $2$. If $n$ is even, $n^2+1$ and $n+1$ are both odd, hence $\gcd(n^2+1,n+1) = 1$. If $n$ is odd, $n^2+1$ and $n+1$ are both even, hence $\gcd(n^2+1,n+1) = 2$.


4

Here is a sketch of a contraposition argument. Suppose that $3$ is not a factor of $m$ or of $n$. Then each is either one greater or one less than a multiple of $3$, i.e., there exist integers $j$ and $k$ such that $m=3j\pm1$ and $n=3k\pm1$ (with independent sign choices). Multiply these together and you will have $3(\text{stuff})\pm 1$, so $mn$ is not a ...


4

Hint: $$5^{2(n+1)}+12(n+1)^2-36(n+1)-1=$$$$=\underbrace{(24\cdot 5^{2n}+24n+12-36)}_{\text{trivially divisible by }24}+\underbrace{(5^{2n}+12n^2-36n-1)}_{\text{inductive hypothesis}}$$ Alternatively, $$5^{2n}+12n^2-36n-1=(25^n-1^n)+12(n^2-3n)$$ Here $25^n-1^n=(25-1)(25^{n-1}+25^{n-2}+\cdots+25+1)$ and $n^2-3n$ is even.


4

By the pigeonhole principle, at least two of the original numbers are equivalent modulo 3 and two are equivalent modulo 5. Thus the product of differences will be divisible by $3\times 5=15$. Similarly, the mod 2 class values may be split 6:0, 5:1, 4:2 or 3:3. In these cases the difference product will have 15, 10, 7 or 6 powers of two included. Thus the ...


3

For any positive integer $n$, let $S(n)$ denote the statement $$ S(n) : 6\mid (n^3+11n). $$ Base step: For $n=1, S(1)$ gives $1^3+11(1) = 12 = 2\cdot 6$. Thus, $S(1)$ holds. Inductive step: Let $k\geq 1$ be fixed, and suppose that $S(k)$ holds; in particular, let $\ell$ be an integer with $6\ell = k^3+11k$. Then \begin{align} (k+1)^3 + 11(k+1) &= ...


3

$$3k^2 + 3k + 12=3(k^2 + k +4)= 3(k(k+1)+4)$$ Can you see why $k(k+1)$ and $4$ are each divisible by $2$? At least one of $k, k+1$ is even, as is $4$, hence $2$ divides $(k(k+1)+4)$, and with three as a factor of $\color{blue}{3}(k(k+1)+ 4)$, we have $$2\cdot 3 = 6\mid (3k^2 + 3k + 12).$$


3

Well the greatest integer that divides that is $n=2001*2002*...*2009$, but assuming you want $n<2001*2002*...*2009$, we move on So $n|2001*2002*...*2009 \iff $ there is a number $s \neq 1$ such that $ n*s=2001*2002*...*2009 $. So For $n$ to be maximal, $s$ must be minimal, as $n=2001*2002*...*2009/s$. If you find $s$, you find $n$.


3

Try to decompose m and n into their prime factorization.


3

When you are doing something like this, the advantages of a brain over a computer are minimal. It is best to admit that and select the algorithm that you can carry out fastest. Creativity will play a minimal role in intuitively recognizing anything but the smallest primes, and any "tricks" would almost certainly correspond to known primality tests and thus ...


3

Start out by assumption to proove the conditional. So now we know that $d | (da + b)$ and we want to proove $d | b$. Our assumption really means that there is an integer, call it $c$, such that $\frac{(da + b)}{d}$ is an integer. That means that $c=a + b/d$ is an integer. An integer plus something else must be an integer only if that something else is an ...


3

Hint $\ $ If $\,f(x)\,$ is a polynomial with integer coef's then $\,n\!+\!1\mid f(n)\iff n\!+\!1\mid f(-1)$ since, by division, $\, f(n) = q(n)(n\!+\!1) + r,\,$ so $\,f(-1) = r\,$ be evaluating at $\,n=-1.$ Therefore $\,n\!+\!1\mid f(n)\iff n\!+\!1\mid f(n)-q(n)(n\!+\!1) = r = f(-1)$ Remark $\ $ If you know modular arithmetic then the proof is more ...


3

I demonstrated this little theorem through the Bézout's theorem: If a prime number $p$ isn't a divisor of $a$, $(a,p)=1$ because the only divisors of $p$ are $p$ and $1$. Then there are two numbers $k$ and $l$ such that: $1=ka+lp$. Multiplying this equality by $b$ we obtain : $b=kab+lpb$ but if $p$ is a divisor of $ab$: $ab=pr$ for some $r\in \mathbb{Z}$ and ...


3

If your polynomials are over $\mathbf{R}$, then a gcd of $1$ is equivalent to a gcd of $2$ (and any other nonzero real), because in general gcds are only well-defined up to associatedness, i.e. mutual divisibility. The greatest common divisor of $f$ and $g$ is (in the case of polynomials) defined as a polynomial $d$ such that $d$ divides $f$ and $g$ and ...


3

For base case $(n=0)$ : $9$ divides $0^3+1^3+2^3=9$. For inductive step : Supposing that $\color{red}{n^3+(n+1)^3+(n+2)^3=9k}$ where $k\in\mathbb Z$, you need to prove that $(n+1)^3+(n+2)^3+(n+3)^3=9m$ where $m\in\mathbb Z$. ...


3

Yes. Another way: $\ a^2\mid a^3\mid b^2\,\Rightarrow\,(b/a)^2 = n \in \Bbb Z\,\Rightarrow\, b/a \in \Bbb Z\,$ by the Rational Root Test. In detail: if $\,x = b/a\,$ is a root of $\,f(x) = x^2 - n\,$ then RRT implies that the least denominator of $\,x\,$ divides $1\ (= $ lead coef of $\,f),\,$ so $\,x\in\Bbb Z,\,$ being a rational writable with denominator ...



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