AoPS Academy
[/quote]
, do not answer with "
is a solution" only. Either you post any kind of proof or at least something unexpected (like "
is the smallest solution). Someone that does not see that is a solution of the above without your post is completely wrong here, this is an IMO-level forum.
be a set of 
elements. Let 
be subsets of such that the union of any 
of them has more than 
elements. Show that there's a member of that occurs in at least 
different subsets 
.
of the set 
, define its colorfulness as the greatest natural number 
such that:
, 
, if 
, then 
.
? Determine how many such permutations have maximal colorfulness.
be a triangle with incenter 
and circumcenter 
. 
the orthocenter of triangle 
. The incircle of touches side 
at 
respectively. Suppose that 
and 
intersects 
at 
and 
respectively (differ from ). Prove that 
lies on a circle. denote the circumcircle of )
table filled with natural numbers, we say it is a divisor table if:
-th row are exactly all the divisors of some natural number 
,
-th column are exactly all the divisors of some natural number 
,
for every .
is given. Determine the smallest natural number 
, divisible by , such that there exists an divisor table, or prove that such does not exist.
, prove that there exist infinitely many pairs of positive integers 
(
) such that![\[
\tau(m^k) \tau(m^k + 1) \cdots \tau(n^k - 1) \tau(n^k)
\]](http://latex.artofproblemsolving.com/b/8/6/b863243eaace4276de6b12b7c5a449f1306b0145.png)
is a perfect square, where 
denotes the number of positive divisors of 
. be a triangle and let 
be a point in its interior. Lines 
, 
, 
intersect sides 
, 
, 
at 
, 
, 
, respectively. Prove that![\[ [PAF]+[PBD]+[PCE]=\frac{1}{2}[ABC] \]](http://latex.artofproblemsolving.com/b/6/f/b6f492b82d7b43d9a5a0a7f9e81205cb8e732bc9.png)
lies on at least one of the medians of triangle . (Here ![$[XYZ]$](http://latex.artofproblemsolving.com/c/7/6/c7608a3e97e44fc5bcf0cd62a1f7dfc0a0a2e7d4.png)
denotes the area of triangle 
.)
, such that:
.
, 
, with 
, 
. Prove that there exists 
such that for every 
![\[
f_n(x) = \frac{x}{1 + nx}, \quad \text{if and only if } f(x) = \frac{x}{1 + x}, \quad \forall x \geq 0.
\]](http://latex.artofproblemsolving.com/0/f/c/0fc36d9264eb7e103128c489aeae521a859c1fd4.png)
(For and , the notation 
represents 
. )
. We show that there are no other solutions. Since must be odd, assume 
. be the least prime factor of . We have 
since is odd. Furthermore, 
.
mod is 
. This is because the order must divide 
, which must equal otherwise must have smaller prime factors which also divide , contradicting 's minimality. Thus, 
, so 
.
to divide 
, we must have 
. Since 
, using the lifting the exponent lemma yields 
. We then conclude that 
, but since 
is the smallest prime factor of , we must have 
.
for some not divisible by 
or . Since , we have 
and we can let be the smallest prime factor of . But similarly to before, we see that 
and thus 
. This means 
. Since 
, we must have 
. is divisible by . However, 
, so we are done.
is the smallest prime dividing , so we have 
. Clearly 
. Let denote the order of 
. Observe that 
, and since 
, we have 
. 
is impossible, which means 
.
is the next smallest prime dividing , we have 
. 
fails upon checking. is the only prime dividing . We need 
, for 
. By LTE, 
.
, which clearly works. 
, which works as well. So, we are done.
. This implies that 
. Also note that 
is a solution so suppose 
. Now take the smallest prime factor of (notice that this can’t be ). We have that 
and also note that 
so this order must be equal to . Hence =3.
where 
and 
is an odd integer. We have: 
But we clearly have 
and from LTE 
hence 
must be qual to so we get that 
.
. Now 
is a solution (
) so suppose that 
. Let be the smallest prime factor of and note that this isn’t or . We similarly get that 
so 
so from minimality this implies 
. Hence 
. In either case, we get that 
so 
which isn’t possible. Therefore the only solutions are and 
.
is odd. dividing then order of modulo divides 
but not and it also divides 
implying the order must be giving that the smallest prime must be the smallest prime.
gives us that 
=
which is greater than 
implying 
where is an odd number not divisible by . Plugging this and using similar order arguments, we get that divides 
which is false implying .
is the only solution.
which clearly works.
and let 
be the smallest prime divisor of 
with 
for 
. Let 
. Since 
, it follows that 
and 
. So 
where 
for all 
. But 
and thus 
. From this it follows that 
for some 
. If 
then 
which is absurd. If 
then from 
it follows that 
which is absurd as well.
and 
. From here it's easy to get that 
. So 
(by LTE 
and thus 
and so 
) and 
. We have 
and let's assume 
and that 
is the smallest prime divisor. Let 
and as before we get 
( cannot be 
because of the same reason as before). If 
then 
but this is impossible. So 
and 
. From this we get 
and so 
. Note that 
, so 
but this is a contradiction since 
. From this contradiction it follows that 
and we get the desired solution set.
, which clearly works.
, where is the smallest prime factor of . But 
, and thus 
stuff that
Now let 
where 
.
where is the smallest prime divisor of 
.
.
is impossible because then 
, and is impossible because 
, and so can never divide the numerator. Thus in fact no such prime exists, and 
.
is an integer 
be the smallest prime divisor of (such a prime exists because 
). because RHS
is the smallest prime divisor of we get that 
so 
and 
we get:
-prime)
so simmilarly as before let be the smallest prime divisor of hence we find that 
however if then:
but RHS
so 
we get:
such that 
hence 
which obviously works 
must be odd, and suppose that . Letting be the minimal prime divisor of , we have 
and thus 
. We also have 
. By minimality , so it follows that 
.
and 
. Then 
from exponent lifting, giving 
. Thus . for , so that 
occurs if and only if . Let be the smallest prime factor of . Then similarly 
. Hence 
, but 
as . and 
as 
. Thus cannot exist; in other words, we have . is thus 
. 
must be odd, and suppose that . Letting be the minimal prime divisor of , we have and thus . We also have . By minimality , so it follows that . and . Then from exponent lifting, giving . Thus . for , so that occurs if and only if . Let be the smallest prime factor of . Then similarly . Hence , but as . and as . Thus cannot exist; in other words, we have . is thus . 
which satisfy the given condition are and . It is clear that these solutions work, so we shall now show that they are the only ones. clearly works, we consider in what follows. Further, the left hand side is clearly odd for all 
so we must have being odd. We first show the following. which satisfies the given divisibility, must be the smallest prime divisor of . denote the smallest prime divisor of . Since 
it follows that 
. Thus, 
. Also, 
so if there exists an odd prime 
we have 
so 
. But, 
so 
which contradicts the minimality of . Thus, 
is a perfect power of two. Now, since 
as is odd we must have 
. Thus,![\[0 \equiv 2^n+1 \equiv 2 +1 \equiv 3 \pmod{q}\]](http://latex.artofproblemsolving.com/8/a/6/8a6f4845b7053180d80012ca1aaa9686bd5f580f.png)
which holds if and only if 
as desired.![\[2\nu_3(n)=\nu_3(n^2) \le \nu_3(2^n+1) = \nu_3(2+1)+\nu_3(n)=\nu_3(n)+1\]](http://latex.artofproblemsolving.com/9/0/b/90bdf0b9fd83642fd3786a834717e2bb493ca69d.png)
which implies that 
. Thus, if is a power of it must be itself, which works. Next, we consider 
and hence, there exists a second smallest prime divisor 
of . As before note that if 
is not a power of two, must have a smaller prime divisor than 
. Thus, can only have factors of and in it's prime factorization. However, as noted before, 
and 
so the only possibilities are 
and 
. The former implies that 
which is a contradiction while the second implies 
which requires 
. Thus we must have 
. But it is not hard to check that 
over all positive integers so this is a contradiction and we are done.
Let be the smallest prime dividing 
If doesn't exist, we get that 
, which is a valid solution. If exists, I claim that 
while 
Thus, 
However, since is the smallest prime dividing 
we have that 
Clearly, the order can't be 1. Thus, the order is 2. Hence, 
Let be the smallest prime dividing 
If exists, I claim that 
. If doesn't exist, we have that 
and thus 
which is indeed a solution.
while 
by Euler's theorem. Thus, 
If it is 1, this clearly doesn't work. If it is 
we have that 
which means that 
If the order is 
this is clearly impossible because we can't have 
. If the order is 
then 
Thus, we have that 
Thus, we have that 
However, we have that 
and hence 
By infinite descent, we are done.
is a solution and suppose that . is odd.
be a prime divisor of , 
. Then:![\[q \mid n \quad \text{and} \quad n^2 \mid 2^n + 1 \Rightarrow q \mid 2^n + 1\]](http://latex.artofproblemsolving.com/7/1/f/71f097ce2d5a4f858faf9e8389e7ece49f0c3ffd.png)
Applying LTE:![\[v_q(2^n + 1) = v_q(2 + 1) + v_q(n) = v_q(3) + v_q(n) = v_q(n)\]](http://latex.artofproblemsolving.com/a/4/d/a4da430806da73d67af9a1273794ae957dc482e0.png)
On the other hand:![\[v_q(n^2) = 2v_q(n)\]](http://latex.artofproblemsolving.com/f/5/1/f5178b99e2a884726d11aa2a3cfc275babdeb6b9.png)
Since , we must have:![\[v_q(n^2) \le v_q(2^n + 1)
\Rightarrow 2v_q(n) \le v_q(n)
\Rightarrow v_q(n) \le 0\]](http://latex.artofproblemsolving.com/4/7/d/47d1f511d8f8499ce6eb6ec363e2e088768f0661.png)
But 
, a contradiction.
, where 
and 
. be an odd prime divisor of 
. Since 
, and , 
.
. So:
satisfies the condition.
and 
Prove that
Prove that
such that![\[ \frac {2^n + 1}{n^2}
\]](http://latex.artofproblemsolving.com/9/2/2/922444e7669c326efcad5fde3ea00f8c2d9fa5d8.png)
is an integer.
be the set of all solutions and 
be the set of all prime factors of the solutions.
is 3.
and let's try to determine the second smallest element 
.
be a multiple of 
.
(otherwise it is easy to get that any power of 
divides 
,
where 
or 
and 
does not have prime divisors smaller than 
,
of 2 modulo 
.
must be even, since otherwise we would have 
,
.
we must have 
or 
.
and 
deliver only one new prime factor 
,
.
,
and thus 
.
Since 2n + 1 | 22n − 1, 
be the smallest prime divisor of 
is obviously solution. Let 
. 
and 
(By the fermat's theorem), we obtain that 
.
is a primitive root modulo 
.
.
.
.
.
.
.
which is a contradiction.If 
then 
.
when 
.
so 
with 
odd
then 
.
wich 
then 
then 
is divisible by 
,
.
.
positive integers such that 
is an integer. Find all 
.
but this is not true for any prime 
and so you can't use LTE here.
and so let 
where 
b
similarly the smallest prime factor of 
is 
and
and we get 
implying 
