AoPS Academy
be a triangle with 
. Let 
be the orthocenter of . Point
is the midpoint of 
and point 
lies on the side 
such that 
. Prove that
.
be a regular polygon, and let 
be its set of vertices. Each point in is colored red, white, or blue. A subset of is patriotic if it contains an equal number of points of each color, and a side of is dazzling if its endpoints are of different colors. is patriotic and the number of dazzling edges of is even. Prove that there exists a line, not passing through any point in , dividing into two nonempty patriotic subsets.
be an integer greater than 
. For a positive integer 
, let 
. Suppose that there exists a 
-element set 
such that is an -element subset of 
; shares at most one common element; is contained in exactly two elements of . in terms of .
, define 
and 
, where 
and 
denote the product and sum of the digits of , respectively. Find all solutions to 
and 
be positive integers satisfying the equation ![$(a, b) + [a, b]=2021^c$](http://latex.artofproblemsolving.com/2/4/6/246ccbb22acecb7adc72219afb8afb34c9b05101.png)
. If 
is a prime number, prove that the number 
is composite.
where 
is a prime number.
. Then, 
and ![$[a,b]=[pd+p,pd]=p[d+1,d]=pd(d+1)$](http://latex.artofproblemsolving.com/2/d/3/2d311f22c9ed2658e674f6b5950f3481e9abec0b.png)
. Hence, 
.
. Hence, the number 
must a perfect square. But, 
and 
. So, this number cannot be a perfect square. Contradiction.
. Hence, the number 
must a perfect square. If 
, again 
. Contradiction. Thus, 
. Then, 
. Hence, 
. Since 
, we find that 
. Then, 
and 
. Clearly, 
, so it is composite.
and ![$[a,b]=[b+p,b]=(b+p)b$](http://latex.artofproblemsolving.com/b/a/a/baa8ab7ae930285634412ebec715b50320bd9253.png)
. Hence, 
. Hence, the number 
must be a perfect square. Let 
where 
. Then, 
and since 
, we find that 
. Then, 
. Suppose that 
where 
is a prime number. Hence, 
. is even.
. Then, 
. But, each prime number can be written in or 
different way as the sum of 
perfect squares. Thus, 
. Clearly, 
so 
. Then 
but 
. Contradiction. is odd.
, then 
. Contradiction. So 
. Then, 
. Contradiction.
where is a prime number.. Then, and . Hence, .. Hence, the number must a perfect square. But, and . So, this number cannot be a perfect square. Contradiction.. Hence, the number must a perfect square. If , again . Contradiction. Thus, . Then, . Hence, . Since , we find that . Then, and . Clearly, , so it is composite. and . Hence, . Hence, the number must be a perfect square. Let where . Then, and since , we find that . Then, . Suppose that where is a prime number. Hence, . is even.. Then, . But, each prime number can be written in or different way as the sum of perfect squares. Thus, . Clearly, so . Then but . Contradiction. is odd., then . Contradiction. So . Then, . Contradiction.
with 
and 
, 
. Assume w.l.o.g. 
(clearly 
). We then have 
for a prime , thus 
. Now, if 
then we obtain that![\[
d\left(b_1^2+b_1+1\right)=43^c\cdot 47^c.
\]](http://latex.artofproblemsolving.com/f/0/3/f0329754b9cc4936c78be6819af35f077e54f44a.png)
If 
, then 
, but 
as 
. Hence, in this case, 
, thus and 
is the only possibility. With this we find 
, for which 
is obtained; and for this solution, 
is divisible by 
, hence is the conclusion.
, , which is handled exactly as demonstrated by Baris. (Let me also add that one way to prove the also contradiction, 
, in the very last step is to use the quadratic reciprocity: 
whereas 
.)
is not . Then 
and 
. Thus 
. Hence or .. The number we want to be composite is 
. Note that if is even, then 
is divisible by 
, done. If is odd, then is 
which is divisible by for odd .. We prove that this is actually impossible. Note that 
, so 
is a QR modulo 
, but that's impossible due to quadratic reciprocity.
. Thus 
and and we want 
to be composite.
. Then can't be odd, otherwise is divisible by . So suppose is even. We have that 
and it's discriminant is 
. Thus the prime is representable as sum of two squares in two ways. But that's impossible (view this as a lemma: if 
, then 
but note that 
, and now we easily see contradiction). ( is impossible, obviously). We have similarly that 
so it's discriminant is 
, but now finish again with quadratic reciprocity modulo .
and be positive integers satisfying the equation . If is a prime number, prove that the number is composite.
and 
,
and suppose that 
different from then:
we have 
and 
.
then 
by the well known lemma:Let 
then if 
we have 
and 
.So 
contradiction. we have and 
which gives
and we have:
(1)and 
.(2)
then (1) 
gives 
using condition (2) we have 
so equation (1) became:
or 
so no solution.
set 
then we have:
or 
.
then it is well known that every prime in the form 
can be written as a sum of two square in a unique way. but it is obvious that 
so contradiction.
.
We have:![$$2021^c=(a,b)+[a,b]=p+\frac{ab}{p} \Rightarrow ab=p \left(2021^{c}-p\right) $$](http://latex.artofproblemsolving.com/7/b/6/7b6bad39eae04929fcf703629aa14d2ca6992448.png)
As 
we have 
and hence 
. In the case , the quantity in question is even and 
so composite. For observe:
and as it follows it is composite. Finally, for observe that 
thus:
and by a direct check neither of these are quadratic residues modulo 
thus this case cannot occur.
We have:![$$2021^c=(a,b)+[a,b]=1+ab \Rightarrow (a+b)^2+4=(a-b)^2+4\left(1+ab\right)=p^2+4 \times 2021^{c}$$](http://latex.artofproblemsolving.com/5/0/9/509258689fd45f22b46e45de656e9bc3caad6aab.png)
Firstly observe if then the quantity is even and so composite. Now consider 
. is evenIn this case, as and 
, it follows 
is composite else we would have a prime written as a sum of two squares in two distinct ways. In this case observe:
but by LQR as 
is a perfect square we have:
which is a contradiction., odd Here we have:
so is divisible by and 
therefore composite.
and 
is prime and then just added the particular case to make it longer? Or did they try solving the general ![$(a,b)+[a,b]=2021^c$](http://latex.artofproblemsolving.com/2/2/9/2294547f17069997231dc3945ab647cb51f19189.png)
and then managed to just do the first two small cases?
Anyways, my only goal while solving this was to shorten the solution as much as possible. I think I succeeded:
We then have two cases: divides 
In other words, let 
and 
Our condition is then equivalent to ![\[\Phi_3(k)=k^2+k+1=\frac{2021^c}{p}\]](http://latex.artofproblemsolving.com/4/4/e/44ef04df4a64633a69caa0de78ee7fb87492bf78.png)
It's well known that for any prime number and positive integer 
only prime numbers congruent to or 1 modulo can divide 
then 
so 
Therefore, and 
After computing, this yields 
Just bash 
does not divide Then, our condition rewrites as ![\[1+a(a+p)=2021^c\iff (2a+p)^2+4=4\cdot 2021^c+p^2.\]](http://latex.artofproblemsolving.com/0/c/3/0c3dc0f71cc9a99d3904e22912c2ab779279b068.png)
Clearly, cannot divide 
so 
which implies that is even.
can be written as the sum of squares in two ways, so it must be composite. then 
which is a contradiction.
and be positive integers satisfying the equation . If is a prime number, prove that the number is composite.
. Since 
, which is a prime number, then there are two possible cases.
for some prime number .
. This implies 
for some 
. Therefore, we get![\[ p(x^2 + x + 1) = 2021^c \]](http://latex.artofproblemsolving.com/5/9/4/594886dea82293a94fd146b95a3d80212aa98bbb.png)
First, we claim that 
. Otherwise, 
. However, is not a QR modulo . Furthermore, this implies that 
, which gives us 
, and this gives 
as a solution. Just check that![\[ (a + b)^2 + 4 = p^2(2x + 1)^2 + 4 = 47^2 \cdot 13^2 + 4 \equiv 0 \pmod{5} \]](http://latex.artofproblemsolving.com/9/d/a/9daa3688131ee71378086cb965af8ef4e513766d.png)
and 
, which implies 
is composite.
.![\[ (a + b)^2 + 4 = (a - b)^2 + 4(ab + 1) = (a - b)^2 + 4 \cdot 2021^c = p^2 + 4 \cdot 2021^c \]](http://latex.artofproblemsolving.com/6/e/a/6ea008664dc30c37d103a7534fb7ec9c71610930.png)
We first claim that 
. Otherwise, then 
, and one can check that is not a QR modulo . We claim that must be even. Indeed, if is odd, then 
.
can be represented as 
as well, and we could quickly check that 
, or otherwise it's composite because it's divisible by 
. We'll finish off by the following claim and conclude that must in fact be composite. modulo has a unique representation as a sum of squares.
for some 
. Then,![\[ (a + bi)(a - bi) = (c + di)(c - di) \]](http://latex.artofproblemsolving.com/0/4/8/04864300471a2a5cf23f0e87dc795c06e5295bbd.png)
Note that ![$\mathbb{Z}[i]$](http://latex.artofproblemsolving.com/c/7/9/c79ec4020beb2bd23555dfd7289612faf19d5959.png)
is a UFD, which implies that 
and 
can't both be primes. WLOG is not a prime. Then, there exists a nontrivial factorization 
. Therefore,![\[ p = N(a + bi) = N(x + yi)N(z + wi) = (x^2 + y^2)(z^2 + w^2) \]](http://latex.artofproblemsolving.com/d/e/a/deae055d41917824267936191c4e8193611dbdf2.png)
contradicting the fact that is a prime.
.
. Let 
and 
. Then we have
.
. Let 
and 
. Then we have
unless . When , we have 
so that
. Let 
so that 
. Note that 
, as otherwise 
and 
would both be even. We have subcases. is odd. Then 
, so 
. Hence 
, and 
. In particular, the discriminant of this quadratic must be a QR mod 
, which we can verify is false with quadratic reciprocity. is even. Then we have
is expressible as the sum of squares in different ways it is composite, as desired.
, then it would be 
. let 
so . But it's well-known that the polynomial 
has no prime divisor in the form 
, but is such number. So and and we should've:
which means 
and 
,
so we can just compute the desired expression and it wouldn't be a prime number. and 
, which means : 
where . if was odd , we're done since it's divisible by . if it was odd , it's well-known that every prime number in the form can be UNIQUELY written as 
for positive integers 
. So 
but by the definition of , we have 
so 
. this is impossible since one of 
for 
should be divisible by which is a contradiction and we're done.
so
and follows from the fact that if 
, 
(clearly 
are not zero modulo ) is the solution of 
in Z_p so 
. Which contradicts 
. Let 
, 
. Notice that 
. Say:
Case 1: 
. This means that 
, so we have 
. If is even:
If was prime, it only can be uniquely represented as a sum of squares, which means 
, however, that means it's even, contradiction. was odd, we have 
. However, this means 
since it's prime, so 
. This means is a quadratic residue mod .
Contradiction.
, we have 
. Furthermore, is prime and 
.
. We have:
We also have 
, which means is a quadratic residue mod 47. We have:
Contradiction.
. We have:
Now, 
. For 
, we are done by the same step as earlier, however if , we have 
. Hence, we are done.
(
obviously cannot happen), then since is a prime and 
we have 
or . Suppose FTSOC that 
was a prime. it means that 
, now if both were even then clearly cannot be a prime as it is divisbile by . Now back to 
where is a prime we also have that 
which means by quadratic formula that:
Now clearly 
is odd so 
, and also notice that 
implies that 
so we in fact get 
, so if we have that 
and is even then as 
must have exactly one representation of the form 
(this can be proven using Thue Lemma), then we have that either 
or 
, of course neither can happen therefore we get a contradiction!. And if is odd then if 
we get that as 
that 
which is a contradiction so 
, but then 
and this is a contradiction as by QR's we have that 
so no such 
should exist, contradiction!.
prime.
and 
and ![$[a,b]=q(x^2+x)$](http://latex.artofproblemsolving.com/f/d/7/fd73ecc1cd2edd5d65c12cf47937fa17ff6e0049.png)
so 
and so 
therefore 
, as an extra notice that if some prime 
then we must have by orders that either 
and 
or 
, but notice that 
so we must have 
and or else 
and that can't happen, which means that we must have 
and it's clear that the only positive solution is therefore 
and 
and thus 
must be prime, but this can't happen as then 
so 
which would mean 
, an obvious size contradiction!. is prime, thus we are done 
.
, prime and 
. For the contrary let 
prime. Then 
, so or ., then ![$ab+1=[a,b]+(a,b)=2021^c$](http://latex.artofproblemsolving.com/6/7/b/67b3c5aa2606ca993007dc1da117a44c49ade903.png)
. If even then 
, which is the contradiction, because a prime number has unique represantion as sum of two squares (I think its Fermat theorem). So if odd then 
, i.e 
, so 
. So our condition becomes 
(in fact ). In other word 
, i.e 
, but 
, which is contradiction., then 
, 
and ![$p(1+b_1(b_1+1))=(a,b)+[a,b]=2021^c$](http://latex.artofproblemsolving.com/f/3/4/f34a846e002beed2104b77dc2869c16747df7134.png)
, so 
or 
. If 
, then 
, i.e 
. So 
, but
,
, i.e 
(), then 
, , 
, 
. And is not prime (because it divisible by 5).
