I
be positive real numbers, show that:
.
be nonnegative positive integers.
triangle with 
.
,
point on AC, AB respectively such that 
,
.
,
lines intersect at point 
.
,
be a trapezoid. By 
we denote the angle bisector of angle 
. Let 
and 
.
is cyclic.
and 
.
be the foot of the interior bissector of 
(its intersection with 
)
calculate the sidelength 
is the remainder obtained by dividing it by 
and 
and it's digits are all different and nonzero. How many piolas are there between 
and 
?
.
is a point on the line segment 
,
and 
are 
and 
respectively. Find the area of 
.
and 
Prove that
Let 
Prove that
and 
divide 
into three equal parts while the points 
and 
divide 
and 
intersect at 
.
and 
intersect at 
.
,
and 
are 
,
,
respectively, find the area of the triangle 
.
passing through 
cuts the circle of diameter 
.
cuts circle of diameter 
and 
,
.
is tangent to the incircle of 
.
.
,
and 
.
.
Y by Davi-8191, Mathuzb, anantmudgal09, Amir Hossein, otsin, HWenslawski, megarnie, Adventure10
Let 
be positive integers such that 
and 
. Let 
be the set of values attained by 
as 
runs through the positive integers. Show that is the set of all positive divisors of some positive integer.
be positive integers such that 
and 
. Let 
be the set of values attained by 
as 
runs through the positive integers. Show that is the set of all positive divisors of some positive integer.This post has been edited 2 times. Last edited by v_Enhance, Feb 25, 2018, 11:06 AM
Reason: LaTeX copy edits
Reason: LaTeX copy edits
.
and the prime 
divides 
.
as well. Consequently, all divisors of 
;
(since otherwise 
too). So WLOG 
.
and construct 
(by Chinese theorem) such that 
for any prime power 
dividing 
.
.
and 
.
is correct. Moreover, since 
,
.
.
is in 
and 
.
,
then ![\[ n \equiv \begin{cases} n_1 \pmod q & \nu_p(k_1) \ge \nu_p(k_2)\\ n_2 \pmod q & \text{otherwise}. \end{cases} \]](http://latex.artofproblemsolving.com/2/e/c/2ecb9f159974ef110bb3493953a3ca62cc8777bd.png)
Then 
for each 
then 
.
,
satisfies the problem conditions then so does 
.
,
,
,
is a divisor of 
.
By CRT, we have a solution 
Therefore, the maximum gcd is at least 
,
.
,
.
is trivial by definition, and the case 
is also trivial.
,
.
,
and we have 
.
.
,
for large enough 
,
.
.
which has not common prime divisors with 
divides 
.
,
and 
.
.
have the highest power of 
,
,
.
where 
?
and 
such that 
and 
with 
,
,
and 
,
.
since we could then use the result above in earlier posts about finding 
for prime 
.
and 
by 
and substituting in terms of 
we have:
then 
,
.
to satisfy the second expression. As said in earlier posts above, since 
is attainable as a 
.
,
.
,
,
,
and 
,
automatically (for any 
as above.
be integers such that 
and 
.
over all pairs
of relatively prime is 
)
where 
is the maximum exponent of any prime 
.
by a simple Hensel's lemma deconstruction on the 
.![\[ \gcd(an+b, cn+d) = \gcd((a-c)n+(b-d), cn+d) \]](http://latex.artofproblemsolving.com/a/a/d/aad440d05374abb3c80893c238e38d5432d60f76.png)
by Euclidean Algorithm. Think of 
and 
,
.
.
,
at all times. Since the sum 
strictly decreases each time we do this operation, and we can flip the two ordered pairs if the first is too small, we must get 
at some point. So we have![\[ \gcd(an+b, cn+d) = \gcd(a'n+b', d') \]](http://latex.artofproblemsolving.com/e/0/4/e04f9c325ad5255986371aff7c524e4c1fc40eb8.png)
for some 
,
and 
(because 
is invariant under the operation, so it must be nonzero at the end, as it was initially), and 
(if not, pull out the gcd). We want to show that 
is the set of all multiples of some positive integer.
,
,
.
or 
,
are pairwise coprime.
.
be some divisor of 
.
.![\[ \gcd(a'n+b', d') = k \iff \gcd(\tfrac{a'n+b'}{k}, \tfrac{d'}{k}) = 1. \]](http://latex.artofproblemsolving.com/0/f/f/0ffb1823cc433dba7d46b418ffe8afe649b7d681.png)
A solution for this is![\[ \frac{a'n+b'}{k} = v\frac{d'}{k}+1 \implies n=\frac{vd'+k-b'}{a'}\]](http://latex.artofproblemsolving.com/3/d/4/3d460e7a87dc48026b200f215ae5b08b9a7d7709.png)
where 
.
,
.![$[0, m]$](http://latex.artofproblemsolving.com/0/7/9/07924a4a265cce088f38ad0549e3adeefa320413.png)
for some 
is 
.
.
,
.
.
,
,
.
.
,
by setting 
.
through 
case is symmetric to this one.
.
;
case is symmetric. Next, note that 
,
.
.![$k\in [0, \nu_p(ad-bc)]$](http://latex.artofproblemsolving.com/b/6/f/b6f4dfa83b0b99370fa47e0c287ee85debae6086.png)
,
;
,
.
,
,
and thus 
,
.
can take on is any integer in ![$[0, m_p]$](http://latex.artofproblemsolving.com/e/3/2/e32db330a18567c7ef24403b56d8c837fb7f7460.png)
,
.![$k\in [0, m]$](http://latex.artofproblemsolving.com/1/e/1/1e11384e8dc13eacc684efb8c1cb501b1d5bf536.png)
,
holds (for instance, in case 3, 
and 
is 
)
be the primes which divide 
for some ![$y_1\in [0, m_{p_1}], ..., y_z\in [0, m_{p_z}]$](http://latex.artofproblemsolving.com/8/d/b/8dbf4e3ff0b7cede474a98748d1991d7d67bb53a.png)
,
,
.
.
and positive integers 
are given such that 
assuming there exists indices 
satisfying 
prove that there exists indices 
such that 
.
is a divisor of 
,
be 
for every prime 
.
)
,
.
.
and we will prove it for 
.
,
.
;
,
we must have that 
are divisible by 
is an integer; note 
so 
,
,
also satisfies 
.
,
such that every term 
.
with 
.
,
we can write 
and 
for relatively prime 
and this gives 
hence 
.
as 
.
.
,
.
and pick some prime 
or else 
contradicting 
.
.![\[n' \equiv n + p^{e - 1} \pmod{p^e}\]](http://latex.artofproblemsolving.com/e/3/1/e31da07dacddf51f0dce5df9a274e7645d66297d.png)
![\[n' \equiv n \pmod Q\]](http://latex.artofproblemsolving.com/b/3/8/b38685dad7feb6dafaabd3e970cdf47dbb6e2633.png)
where 
and that due to 
the exponents of the other primes do not change, completing our inductive step.
by 
in the 
However, one can quickly see this doesn't necessarily work because possibly 
So how do we remedy this? By force!
it is possible to always pick a 
This is fortunately super simple to prove: at some point we reduce to 
and as long as 
this is always possible. But this is really equivalent to 
and 
Now note that 
by Euclidean Algorithm, so the 
and 
so there will be no problem multiplying the former by 
and the latter by 
in the first and second terms of the original problem, respectively. Then we get 
Since 
is relatively prime with 
the first term covers the residue set of 
is a linear combination of 
hence the 
.
,
as well. WLOG 
.
we end up with 
because 
.
because 
)
.
are reachable.
so the periodicity is evident (and the periods are relatively prime so no issue there). Thus 
.
.![\[\gcd(an+b,cn+d)\mid \frac{c}{\gcd(a,c)}(an+b)-\frac{a}{\gcd(a,c)}(cn+d) = \frac{bc-ad}{\gcd(a,c)}\]](http://latex.artofproblemsolving.com/2/5/3/25336bf5f4b8f81cffa9a81b3b03efb7a2d38d67.png)
Thus, all 
satisfy 
.
.
,
solutions to 
.
to![\[an+b\equiv 0 \pmod{q}\]](http://latex.artofproblemsolving.com/5/d/5/5d51c135b4f10f02a64bd7951c201c12a45a5306.png)
because 
.![\[\frac{c}{\gcd(a,c)}(an+b)\equiv \frac{a}{\gcd(a,c)}(cn+d) \pmod{q}\]](http://latex.artofproblemsolving.com/c/4/1/c4184b83f1d89ed5d98702925a4b9c86efc9ba8e.png)
Thus, if 
,
.
which will also work, so there are exactly 
,
.
is determined by 
.
,
,
.
,
.
.
,
such that both 
divide 
.
,
.
.
,
,
such that 
,
.
,
and 
,
meaning that 
Then 
and therefore 
to occur for any 
because then 
which is not possible by definition and moreover, 
for some 
such that 
,
and notice that 
for all 
.
there exists 
for all 
which then suffices by CRT.
to divide both 
and also make sure that 
as we know that 
and we can then again vary 
within 
as in the initial case where 
.
and 
.
,
and 
,
.
,
and 
meaning that 
and consequently, whenever 
for some 
,
,
,
,
.
.
one can satisfy 
and taking 
for some 
,
as 
for all 
and in fact we can set 
for any 
and we can then satisfy the desired equality for any 
as desired. 
can be attained, then all powers of 
and 
.
for some positive integer 
,
similarly. There will only exist 
.
for 
must also be true, and since the cycle lengths of 
,
for all 
.
.
,
,
If 
and 
are still both multiples of 
.
in case 1 in the 
that are relatively prime, if 
,
.
for some 
-- in this case, the GCD will equal 
line up mod 
such that
Equating for 
The RHS must be a multiple of 
and 
,
be the largest integer such that there exists a multiple of 
in 
be the smallest positive integer such that 
.
for all 
.
for all 
gives 
and 
,
gives 
,
,
.
,
.
,
and 
.
,
.
,
we have 
,
if 
)
)
for some integers 
and 
and 
since we already got that the gcd's are bounded. We have 
since otherwise after going back the steps we are going to get that 
,
be the largest divisor of 
.
,
.
.
,
,
when 
can take all the divisors 
for some 
.
,
Let 
and 
.
Which is further equivalent to
Let 
.
Which gives
As 
(just by definition of 
)
.
,
is bounded 
,
such that
dividing 
and 
are in 
is in 
take 
of 
,
![\[ \gcd(an+b,cn+d) = \gcd(an+b,(a-b)n+(c-d) = \cdots = \gcd(\ell(n),M) \]](http://latex.artofproblemsolving.com/4/c/7/4c74b2c6a1d7ed2b540e4b8dd68a9003958851ac.png)
For some linear function 
and a positive integer 
obtains maximum value an an integer with prime factorization 
.
for any sequence of non-negative integers 
obeying 
.
.
,
.
.
.
which divides 
,
,
(there exists a positive integer solution to this since you can just add 
for some integer 
,
.
,
.
.
and 
.
,
with 
and the problem remains unchanged. Now, note that 
and 
since we are given that 
.
since if 
,
,
,
,
,
so 
,
,
(note that 
,
)
,
,
,
,
,
and 
.
for any positive integer 
,
,
and then 
and 
,
,
,
.
Take some positive integer 
.
so 
for 
.
,![$$\gcd((a-c)(m+k) + (b-d), c(m+k) + d) = \gcd((a-c)m + [(a-c)k+(b-d)], cm + [ck+d])$$](http://latex.artofproblemsolving.com/2/7/0/27045ac47f9743209a253d3cd6b6fbc394311f9b.png)
for all positive integers 
are positive integers, 
,
,
,
,
,
,
,![$$(a-c)(ck+d) = c(a-c)k - cd + ad \neq c(a-c)k - cd + bc = [(a-c)k+(b-d)]c,$$](http://latex.artofproblemsolving.com/3/6/1/361d5f05649e2471c39aa55f1149d1632e5c725b.png)
since 
,
are positive integers and 
is as well since 
.
,
,
and the problem remains unchanged. Then, note that 
Now, let 
(If 
,
by convention.) I claim that 
Note that 
since if a prime 
,
,
,
.
,
,
,
,
and 
,
,
)
Now, note that 
,
,
,
.
so 
,
has to be a divisor of 
such an 
so if 
for some integer 
as 
.
,
,
.
and we'll prove that there exists 
for all 
or 
.
,
,
,
by CRT, we have 
for all 
.
.
using the transforms ![\[ T_1 = \begin{bmatrix} 1 & 0 \\ -1 & 1 \end{bmatrix} \]](http://latex.artofproblemsolving.com/5/9/2/592f08a9e3668d765b442fd1260a1f1049d16ccc.png)
![\[ T_2 = \begin{bmatrix} 1 & 1 \\ -1 & 0 \end{bmatrix} \]](http://latex.artofproblemsolving.com/8/5/a/85a4e0e52a15badca3ac59ff56a0ce464f639953.png)
![\[ T_3 = \begin{bmatrix} 1 & 1 \\ 0 & -1 \end{bmatrix} \]](http://latex.artofproblemsolving.com/e/d/7/ed7e2dea9a53eaaa4071d53aacc2c892e6f29b53.png)
![\[ T_4 = \begin{bmatrix} 0 & 1 \\ 1 & -1 \end{bmatrix} \]](http://latex.artofproblemsolving.com/8/0/b/80bbe84b4a8629e7adb54f4ed3bb618f53b2a40f.png)
all of which have determinant 
.
for integers 
,
over all positive integers 
by scaling. By Bezout's identity, it is easy to see that ![\[ m := \frac{b}{\gcd(b, c^{\infty})}. \]](http://latex.artofproblemsolving.com/f/d/d/fdd26b4384178db650fbab875ec57faa291ebd0a.png)
By CRT, it can be shown that all divisors of 
.
,
.
.
is of the form 
,
.
,
.
,
divide some prime, then 
since it won't divide 
as unbounded, so 
can range anywhere from 
.
.
.
,
,
.
Hence we get that 
,
.
and 
both equal 
and 
more than 
hence all divisors are in 
where 
.
to get
Thus 
.
as well. Since the determinant of the matrix didn't change, 
,
as 
.
for 
.
,
will cycle through all residues mod 
,
.
as well. Then, 
and 
,
.
are exactly divisors of 
.
we claim some element of 
.
then choose 
such that 
and 
.
and 
.
.
we have 
,
choose 
where 
.
but 
does not divide one of them. Thus choosing this across all 
Hence, 
Let 
I claim that 
I claim that 
satisfies our claim. Note that 
while 
and so 
Clearly, all other ones don't change. Hence, our claim is true. Hence, we can also state that 
as ![$[a, b].$](http://latex.artofproblemsolving.com/8/2/0/820bbe08d3de75fa43c3fbcb66725e593eea643c.png)
Let 
We pick 
and 
:![\[ n \equiv \begin{cases} n_1 \pmod q & \nu_p(x) \ge \nu_p(y)\\ n_2 \pmod q & \text{otherwise}. \end{cases} \]](http://latex.artofproblemsolving.com/d/1/3/d1340646f22e5a5fb9c41b5ca210316aaf04d4ab.png)
This forces ![$[x, y]\mid n.$](http://latex.artofproblemsolving.com/a/4/e/a4e3149522910c78dd002176614ffcb4b51f38ef.png)
Thus, we are done.
