# Tag Info

12

Claim. $a+b+c\mid a^{2^n}+b^{2^n}+c^{2^n}$ for all $n\geq0$. Proof. By induction: True for $n=0,1$ $\checkmark$. Suppose it's true for $0,\ldots,n$. Note that ...

5

The observation you make in your question isn't quite right: Given that $a\mid m$ and $b\mid m$, there exist integers $s$ and $t$ such that $$as=m\qquad\text{ and }\qquad bt=m.$$ Also, when you say that $\gcd(a,b)=1$ implies $1=as+bt$ you should be careful using the same letters $s$ and $t$ as before; they need not be the same numbers! In stead you can say ...

4

Start from Bézout's identity: since $a,b$ are coprime, there exist integers $u,v\in \mathbf Z$ such that $ua+vb=1$, whence $$m=uam+vbm.$$ If $a\mid m$ and $b\mid m$, there exist integers $m_1,m_2$ such that $\;m=am_1,\enspace m=bm_2$. Combining with the above equation, we have: $$m=uabm_2+vbam_1=ab(um_2+vm_1).$$

3

Let $S=\{n+1,n+2,\ldots,2n\}$. The claim is that $|S|$ is maximal. To prove this, form descending sequences starting with each term in $S$, where each sequence is finite and ends on an odd term and the term in any sequence is the previous term divided by 2. Denote each sequence by its starting term, e.g. \begin{align} S^{(2n)}&=\{2n,n,\ldots\} \\ ... 3 If (x,y,z)=(a,b,c) is a solution of 4x+3y+2z=2000, then (x,y,z)=(a+1,b+1,c+1) is a solution of 4x+3y+2z=2009. Now find the number of the solutions (x,y,z) of 4x+3y+2z=2009 such that either x,y or z equals 1. (note that this is m-n.) 3 HINT:z=100^2-x^2=(100-x)(100+x)$$As (100-x)+(100+x)=200,100\pm x have same parity and if one is divisible by 3,the other is not So if 2|z,100\pm x must be even If 3|z,3|(100-x)(100+x)\implies either 3|(100-x)\iff x\equiv1\pmod3 or 3|(100+x)\iff x\equiv-1\pmod3 2 If p^2=3m for some m\in \mathbb Z, then p=3k for some k\in \mathbb Z. Suppose otherwise. By Division Algorithm, p=3k+1 or p=3k+2. Squaring p, we get either 9k^2+6k+1 or 9k^2+12k+4 which are both not multiples of 3, contradicting the assumption. Thus, p has to be a multiple of 3. 2 Assuming the result for smaller x+y+z, it is inductively true in the case that any of x,y,z is divisible by 3; this answer is a work in progress. Expand and simplify to obtain:$$\frac{xy+yz+xz}{x^2+y^2+z^2} = \frac{1}{3n}$$or equivalently$$3n(xy+yz+zx) = x^2+y^2+z^2$$But the only way a sum of three squares can be a multiple of 3 is if all of ... 2 c|ab means that ab=q\cdot c, not the other way around! Therefore, you have ab=q\cdot c and ab x + c y = d which you can rewrite into$$qcx + cy = d\\ c(qx+y) = d$$Can you continue from here? 2 It seems that there's a partial solution. Suppose that \mathrm{gcd}(a,a+b+c)=\mathrm{gcd}(b,a+b+c)=\mathrm{gcd}(c,a+b+c)=1. Then for n=k\cdot \phi(a+b+c)+1 \, (k=1,2, \ldots ), where \phi is Euler's function, we have:$$ (a^n+b^n+c^n)-(a^2+b^2+c^2)=a^2 (a^{n-1}-1) + b^2 (b^{n-1}-1) + c^2 (c^{n-1}-1),  where all round brackets are divisible by ...

2

There's one more solution (it isn't mine). One can even prove that $(a + b + c) \mid (a^n + b^n + c^n)$ for all $n=3k+1$ and $n=3k+2$. It's enough to prove that $a + b + c \mid a^n + b^n + c^n$ => $a + b + c \mid a^{n+3} + b^{n+3} + c^{n+3}$. The proof is here: https://vk.com/doc104505692_416031961?hash=3acf5149ebfb5338b5&dl=47a3df498ea4bf930e ...

2

You're most of the way there. You've observed that $b$ is even. Now consider that $0 \leq c \leq 9$, so $17b$ must be no more than $18$ less than a multiple of $30$. Both $17 \times 2 = 34$ and $17 \times 4 = 68$ fail to qualify, so that leaves $17 \times 6 = 102$ and $17 \times 8 = 136$. These two yield $a = 4, b = 6, c = 9$ and $a = 5, b = 8, c = 7$, ...

1

You know that $30a=17b+2c$ and hence that $b$ is even. Setting $b=2d$, we have $15a=17d+c$, where $d\in\{1,\ldots,4\}$. Since there are only four possibilities for $d$, trial and error is the way to go. If $d=1$, we have $15a=17+c$, which has no solution with single digit $c$. If $d=2$, we have $15a=34+c$, with the same problem. If $d=3$, we have ...

1

The usual articulation of the result you ask about is Euclid's lemma. Changing your notation slightly, Euclid's lemma says that if $p$ is prime, $a$ and $b$ are integers, and $p$ divides $ab$, then $p$ divides $a$ or $p$ divides $b$. Particularly, if $p$ divides $a^{2}$, then $p$ divides $a$. Of course, if $p = 3$ it's also fine to do case by case analysis ...

1

I advise not doing a proof by cases. That was my initial attempt, but I found myself going through a logical rabbit hole with no end in sight. I suggest attempting to show that the common divisor, call it $d$, satisfies $d\leq2$, which implies that $d=1$ or $2$. Here is a proof using the above strategy. Here are a few lemmas that will assist us in our ...

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