Tag Info

Hot answers tagged

15

One can prove this for all integers greater than $1$ by induction: we know that $2$ is a prime. Now for ou inductive step assume that for all $i<n$, $i$ is either prime or divisible by a prime. Case 1: $n$ is prime; we're done. Case 2: $n$ is composite, so $ab = n$ for $a, b < n$. So each of those is divisible by a prime. We're done. Essentially the ...


10

Call the numbers we are looking for good. A number is good if it is divisible by $7$ but not by $11$, or divisible by $11$ but not by $7$. That's what "divisible by exactly $1$ of $7$ and $11$" means. Let $a$ be the number of numbers from $1$ to $999$ which are divisible by $7$, and let $b$ be the number of numbers which are divisible by $11$. If we add ...


7

Since $$\begin{align}(n+1)(n+2)(n+6)-n(n+1)(n+5)&=(n+1)\left\{(n^2+8n+12)-(n^2+5n)\right\}\\&=(n+1)(3n+12)\\&=3(n+1)(n+4)\end{align} $$ we have $$(n+1)(n+2)(n+6)=n(n+1)(n+5)+3(n+1)(n+4).$$


6

$$\gcd(3a,b) = \gcd(a,b)\gcd\left(3,\frac b{\gcd(a,b)}\right)$$ This is the specifics of the formula in the other answers - $\gcd(3a,b)=3\gcd(a,b)$ exactly when $3$ is a factor of $\frac{b}{\gcd(a,b)}$, otherwise $\gcd(3a,b)=\gcd(a,b)$. More generally: Theorem $$\gcd(an,b) = \gcd(a,b)\gcd\left(n,\frac b{\gcd(a,b)}\right)$$ Proof: It's easy to show that ...


5

Hint: How can you factorize $x^{ab}-1$ (see $x^{ab}$ as $(x^{a})^b$)


5

Rewrite as $f(n)=10\cdot 8^{n-1}+3^{3n-1}$ to clear the fraction. Then can you see that $f(n+1)=10\cdot 8^n+3^{3n+2}=8f(n)+(27-8)3^{3n-1}$ We choose the factor $8$ (we could also have chosen $27$) since we want to get rid of one of the exponentials altogether in the $f(n)$ term, and to find that the other one ends up with a coefficient divisible by $19$. ...


4

Remainder theorem: Take $n$, divide by $3$. The remainder is either $0$ or $1$ or $2$. If remainder is $1$, then $n=3q+1$ by long divison if you like. If remainder is $2$ then $n=3x+2=3(x+1)-1$.


4

You actually only need to know that $ar+bs=1$, it then follows that $$\gcd(a,b)=\gcd(a,s)=\gcd(r,b)=\gcd(r,s)=1.$$ A proof is as follows: the $\gcd$ of $a,b$ divides the expression $ar+bs$, since it divides both $a$ and $b$. Therefore it divides 1, which means it must be equal to 1. You then perform similar arguments replacing the pair $(a,b)$ with $(a,s)$, ...


4

One way is that the assumption implies that $x$ must be odd, so $x=2n+1$ and thus $$x^2=4n^2+4n+1$$


4

Suppose $2\mid (x^2-1)$. Then $2\mid (x-1)(x+1)$. By Euclid's lemma, either $2\mid (x+1)$ or $2\mid (x-1)$. But $x+1$ is even if and only if $x-1$ is even. Thus, both must be even. The product of two even numbers must be divisible by four, so $$4\mid (x^2-1)$$


4

$x-1$ and $x+1$ are separated by $2$ so they are either both odd or both even. The first case means that the product will not be divisible by two, so the second case must hold true. Hence $2|(x-1)(x+1) \implies 2|(x+1)$ and $2|(x-1)$ so $4|(x-1)(x+1)$.


4

$$2|(x^4-3) \iff 2|(x^4-3-6) \iff 2|(x^2-3)(x^2+3)$$ Since $2$ is prime it must divide one of those factors. And $$2|(x^2+3)\iff 2|(x^2+3-6) \iff 2|(x^2-3)$$ So $2$ divides $both$ factors if it divides either one!


4

Hint: $n$, $(n+1)$, $(n+2)$, $(n+3)$, $(n+4)$, $(n+5)$ are all 6 consecutive numbers so one of them is a multiple of 6, and 3 of them are a multiple of 2; and 2 of them are a multiple of 3...


4

This is nearly the content of the Coin Problem for two denominations, which just asks which is the largest integer which cannot be realized this way, and it turns that the answer (the "Frobenius Number" for $(r, s)$) is $rs - r - s$. This result reduces your problem to checking a finite number of cases, and in practice this is easy to do by hand for small ...


4

Lemma $\ $ The least factor $>1\,$ of $\ n>1\,$ is prime. Proof $\ $$\,n>1$ has at least one factor $> 1,\,$ viz. $\,n.\,$ Let $\,p\,$ be its least factor $>1.\,$ Then $\,p\,$ is prime (else $\,p\,$ has a proper divisor $\,1 < d < p\,$ and $\,d\mid p\mid n\,\Rightarrow\,d\mid n,\,$ contra minimality of $\,p).$ Remark $\ $ More ...


4

Let $a$ and $b$ be positive integers. Then we cannot find integers $x$ and $y$, both positive, such that $\gcd(a,b)=ax+by$. For if $x$ and $y$ are positive, then $ax+by\ge a+b\gt\gcd(a,b)$. Remark: If the gcd of $a$ and $b$ is $1$, and $c$ is large enough (greater than $ab-a-b$) then we can find non-negative $x$ and $y$ such that $ax+by=c$. You can find ...


3

$(n^2+20,2n+1)=(4n^2+80,2n+1)=(81,2n+1)$. It's easy to show that any divisor of 81 is possible. And from the information above we can see that it's the all possible numbers. So the answer is $1,3,27,9,81$


3

For primes $p > 5$, the Binet formula applies mod $p$, in the following sense. If $p \equiv \pm 1 \mod 5$, $5$ is a quadratic residue mod $p$, and $z^2 - z - 1$ has two roots $\phi_\pm = (1 \pm \sqrt{5})/2$ in ${\mathbb Z}_p$. Then $F_n \equiv ((\phi_+^n - \phi_-^n)/\sqrt{5} \mod p$. In particular, $F_{p-1}$ is divisible by $p$, so $\gcd(p, F_{p-1}) = ...


3

First, show that $\phi$ is a homomorphism. From there, proceed by contradiction: If $\phi$ were not an automorphism, then $\phi$ could not be injective. That is, $x^n = y^n$ for some $x \neq y$. With some re-arranging, we'd have $(xy^{-1})^n = e$. There is a contradiction here. Think Lagrange.


3

Let the highest powers of $p$ in $a,b$ be $A(\ge0),B(\ge1)$ respectively, So, we have $2A=3B\implies \dfrac{2A}3=B\implies 3|2A\implies 3|A\implies A\ge3$


3

Hands on: $p|b$ so that $b=pd$ $p|a^2$ so $p|a$ and $a=pc$ whence $p^2c^2=p^3d^3$ or $c^2=pd^3$ Now $p|c^2$ so $p|c$ and $c=pe$ whence $p^2e^2=pd^3$ or $pe^2=d^3$ So that $p|d^3$ so that $p|d$ and $d=pf$ so that $pe^2=p^3f^3$ or $e^2=p^2f^3$ and $p|e^2$ so that $p|e$ and $e=pg$ Now we have $a=pc=p^2e=p^3g$ Note $p|xy$ implies $p|x$ or $p|y$ is ...


3

For $n+1$ step, we have $$\begin{align}\frac 54\cdot 8^{n+1}+3^{3(n+1)-1}&=\frac 54\cdot 8^{n+1}+8\cdot 3^{3n-1} -8\cdot 3^{3n-1}+3^{3n+2}\\&=8\left(\frac 54\cdot 8^n+3^{3n-1}\right)+(3^3-8)\cdot 3^{3n-1}\\&=8\left(\frac 54\cdot 8^n+3^{3n-1}\right)+19\cdot 3^{3n-1}.\end{align}$$


3

Let's look at a smaller example: the positive integers less than $10$ that are divisible by exactly one of $2$ and $3$. Well, $2, 4, 6, 8$ are divisible by $2$, and $3, 6, 9$ are divisible by $3$. There are $6$ positive integers that are less than $10$ that are divisible by $2$ or $3$. But, $6$ is divisible by both $2$ and $3$. We only should consider ...


3

Try using B├ęzout's identity. Since $\gcd(c, a) = d$, we know that there exist $s,t \in \mathbb Z$ such that: $$ cs + at = d \iff bcs + abt = bd $$ Since $ c \mid ab$, we know that there exists some $x \in \mathbb Z$ such that $cx = ab$, so: $$ bd = bcs + (cx)t = c(\underbrace{bs + xt}_{\in ~ \mathbb Z}) $$ Hence, $c \mid bd$, as desired.


3

Note that $n(n+1)(n+5) = n(n+1)(n+2+3) = n(n+1)(n+2) + 3n(n+1)$. Now $n(n+1)(n+2)$ is always a multiple of $3$ and so is $n(n+1)(n+5)$, being a sum of two multiples of $3$.


3

The statement is, in fact, false. To prove a statement is false, you need only provide one counter-example. (One counter-example suffices, because the claim is being made about any/all integers $a, b, c$ such that $a\mid c$ and $b\mid c$. So if you find any particular triplet such that $a, b, c$ are integers and $a\mid c$ and $b\mid c$, but it is not the ...


2

Hint: $$a^{n+1}-b^{n+1}=a(a^n-b^n)+b^n(a-b)\ .$$


2

For a number to be divisible by $4$, the last 2 digits have to form a 2-digit number that is divisible by $4$. This should simplify things a lot. The trick for $11$: you already know. And if $ABCD$ is divisible by both $4$ and $11$, it is divisible by $44$.


2

When we are working with a prime modulus, we can use the fact that $p|ab$ implies that either $p|a$ or $p|b$. In terms of modular arithmetic this is the same as $ab\equiv 0 \mod p$ implies $a\equiv 0$ or $b\equiv 0$. Here we can use this observation to avoid having to deal with lots of cases. Note that the first equation is equivalent to: ...


2

$\begin{eqnarray}{\bf Hint}\ \ \ {\rm mod}\ 19\!:\,\ \ 3^3\equiv\, 8\ \Rightarrow\ 3^{3n}\!\!&\equiv& 8^n\\ \\ {\rm and}\quad\ 4\,\equiv\, -5\cdot 3\ \Rightarrow\ \dfrac{1}3&\equiv&\!\! {-}\!\!\dfrac{5}4\\ \\ {\rm multiplying \ \, yields}\,\ \ 3^{3n-1}\!&\equiv&\!\! -\!\dfrac{5}4 8^{n}\quad {\bf QED}\end{eqnarray}$ Remark $\ $ As ...



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