AoPS Academy
on 
without derivative.
of positive integers is called cardinal if contains the integer 
where denotes the number of distinct elements in . Let 
be a function from the set of positive integers to itself such that for any cardinal set , the set 
is also cardinal. Here denotes the set of all integers that can be expressed as 
where 
. Find all possible values of 
amazing, if one can partition the set 
into nice subsets.
is not divisible by 
for any positive integer .
is even then 
but 
, impossible, so is odd, and clearly 
fails. Now we claim all 
fail. To see why, note that![\[-1 = \left( \frac{2^n+65}{5} \right) = \left( \frac{5}{2^n+65} \right) = \left( \frac{5^n}{2^n+65} \right),\]](http://latex.artofproblemsolving.com/5/f/8/5f870ab02b5740d8954f5634fb5eadf538ced09d.png)
this in turn equals![\[\left( \frac{3^n}{2^n+65} \right) = \left( \frac{3}{2^n+65} \right) = \left( \frac{2^n+65}{3} \right) = +1,\]](http://latex.artofproblemsolving.com/4/0/f/40fc6dae5bcae9e94e8065f24709306873e1fbe1.png)
. Since 
and 
, we get 
. Therefore, 
for some 
and 
, implying 
, so 
. Clearly, 
, so 
. However, we also have
contradiction. Therefore, 
for all .
. By taking modulo 
, is odd, and it is clear that fails, so assume 
. Therefore, if 
, 
must be a quadratic residue modulo . However, letting 
denote the Jacobi symbol, by quadratic reciprocity we have
contradiction. 
denotes the Jacobi symbol.
fails, assume that 
. Note that 
. even fails, as would divide 
but cannot divide 
. Now assume is odd.
is equal to 
(since 
), since is odd, this implies 
.![\[\left( \frac{5}{2^n + 65} \right) = \left( \frac{2^n + 65}{5} \right) = -1\]](http://latex.artofproblemsolving.com/e/f/8/ef8896e3aa4d52f445ba0f2436f104b7919b63da.png)
and ![\[\left( \frac{3}{2^n + 65} \right) = \left( \frac{2^n + 65}{3} \right) = \left( \frac{1}{3} \right) = 1,\]](http://latex.artofproblemsolving.com/f/d/2/fd2db7a2fddc11e59bb9ee0ff66b6d4f156b46c8.png)
absurd. is to let 
be a prime dividing . Then 
. Since this is true for all primes 
, we have the desired result.
. Assume for contradiction that there exists a solution for 
.
of the fractional expression, it is clear that must be odd (because otherwise divides the denominator but not the numerator). Let denote the Jacobi symbol henceforth.
, and as is odd, it is clear that 
must be a quadratic residue (mod ). But:
a contradiction, and we conclude. 
such that 
. If is even, then is a multiple of , impossible. So is odd. be a prime dividing . Obviously 
. Then![\[p\mid 2^n+65\mid 5^n-3^n\mid 15^n-9^n,\]](http://latex.artofproblemsolving.com/d/1/5/d15b48633e59d860c6db451aac45ba18cc2101f5.png)
so 
is a QR mod .![\[\left(\frac{p}{3}\right)\left(\frac{p}{5}\right)=\left(\frac{15}{p}\right)\left(\frac{p}{15}\right)=(-1)^{(p-1)/2}.\]](http://latex.artofproblemsolving.com/3/6/8/3684b0ac02ea9e40fa68976f9aab6c9ac7e2a05c.png)
Caseworking, we get that mod 
is one of 
. Under further inspection, we note that 
is closed under multiplication mod , so mod is also in . So 
mod is in![\[\{2,6,12,38,44,48,54,56\}.\]](http://latex.artofproblemsolving.com/6/9/7/6971591c7e67473776d844e2db9d6d79c0be1776.png)
Since it must be a multiple of 
and not a multiple of , it must be one of 
. But that means is or mod 
, impossible since is odd. 
and 
with arbitrary odd positive integers, say 
and 
, and see how well this problem generalizes. For even, you want 
, so 
; also you want 
. For , you just want 
. For odd with , applying Jacobi symbol, you want that
For a huge convenience, you also want 
, so
We can now pick 
and 
(as in the original problem). In summary..., , 
, , and , then 
does not divide 
for any 
., , , and , then does not divide for any .
such that 
is an integer. By taking mod , must be odd. Clearly, fails. Let 
denote the Jacobi symbol. We then have that 
and 
forces odd. We have for 
![\[\left(\frac{5\cdot 3^{-1}}{2^n+65}\right)=\left(\frac{5}{2^n+65}\right)\left(\frac{3}{2^n+65}\right)=\left(\frac{2^n+65}{5}\right)\left(\frac{2^n+65}{3}\right)=(-1)(1)=-1\]](http://latex.artofproblemsolving.com/8/6/b/86bcd52aecabb2ce6301131cdbe26a6c03e0360f.png)
a contradiction because we need 
.
is even, then 
but 
contradiction. Since 
we get 
odd number.
then we get 
mod 
Now let us introduce the jaccobi symbol. We get
mod 
we get 
mod 
we get 
mod 
and 
so 
a contradiction
is not divisible by for any positive integer .
is the Jacobi symbol such that
If 
Since 
is even:
Since is odd 
is a perfect square
does not divide for any positive integer has to be odd, because if it is even then 
which is a contradiction, 
works. does not work for size reasons. And also even does not work because we get 
, which I think is wrong as far as I know.![\[\left(\frac{5^n}{2^n+65}\right)=\left(\frac{3^n}{2^n+65}\right) \iff \left(\frac{5}{2^n+65}\right)=\left(\frac{3}{2^n+65}\right) \iff \left(\frac{2^n+65}5\right)=\left(\frac{2^n+65}3 \right) \iff \left(\frac{2^n}5 \right)=\left(\frac{2^n-1}3\right)\]](http://latex.artofproblemsolving.com/b/a/f/baf2a4bc9134af58cda52621f20ef9f93ca6550d.png)
which is obviously false for odd because it implies 
but 
, a contradiction.
is even we get a contradiction, so is odd and 
3., and.
is even then 
is divisible by which doesn't divide . is odd. This implies 
.
.
is odd, hence 
. As:![\[\left\{\begin{array}{cl}
2^n \equiv 1&n \mbox{ odd} \\
2^n \equiv 2&n \mbox{ even}
\end{array}\right.\]](http://latex.artofproblemsolving.com/d/c/d/dcdc566ae7b16289b31e9d45aeee702332eb4596.png)
and for 
, we must have odd.
, we have:![\[\left\{\begin{array}{cc}
2^n\equiv2&n\equiv1\pmod{4} \\
2^n\equiv4&n\equiv2\pmod{4} \\
2^n\equiv3&n\equiv3\pmod{4} \\
2^n\equiv1&n\equiv4\pmod{4} \\
\end{array}\right.\]](http://latex.artofproblemsolving.com/e/e/7/ee7b609b9b4db429b144556131c31331ca82a4e2.png)
and as is odd, 
, consequently 
, implying 
is 
.![\[\left( \frac{(\frac{5}{3})}{2^n +65}\right) \equiv \left( \frac{5}{3}\right)\left( \frac{5}{2^n+65}\right)\equiv \left( \frac{2^n+65}{5}\right)\equiv\left( \frac{\{2,3\}}{5}\right)\]](http://latex.artofproblemsolving.com/d/2/6/d26813ee5384d0bbbc1b3cfcd2a912b362dfd5fd.png)
but: ![\[\left( \frac{2}{5}\right), \left( \frac{3}{5}\right)\equiv -1\]](http://latex.artofproblemsolving.com/7/e/1/7e13d0bdd2db23ecc967fb180f329cb14896eae5.png)
therefore as: ![\[\left( \frac{(\frac{5}{3})}{2^n +65})\right)=\prod_{p\mid 2^n +65}\left(\frac{(\frac{5}{3})}{p}\right)\]](http://latex.artofproblemsolving.com/4/6/3/463736310d66caf77486cce83b8296e3640f19aa.png)
there exists 
prime such that 
isn't 
, contradicting the fact that is 
is even, then 
contradiction is odd. Specifically, we can get that 
This implies is a quadratic residue modulo 
However,
which is a contradiction.
works. is odd. is even. Then, 
, but . be a prime factor of . Then,![\[\left(\frac{5}{p}\right) = \left(\frac{5^n}{p}\right) = \left(\frac{3^n}{p}\right) = \left(\frac{3}{p}\right).\]](http://latex.artofproblemsolving.com/0/9/c/09c237c543ca946e56041906c1712aebd75bc730.png)
and 
be positive integers such that 
and every prime factor of is 
and every prime factor of is 
.
. Then, by quadratic reciprocity, 
.
. Then, by quadratic reciprocity, 
.
with 
prime.
, 
is even.![\[\left(\frac{b}{5}\right) = \prod_{i=1}^k \left(\frac{p_i}{5}\right) = \prod_{i=1}^k -\left(\frac{p_i}{3}\right) = \prod_{i=1}^k \left(\frac{p_i}{3}\right) = \left(\frac{b}{3}\right).\]](http://latex.artofproblemsolving.com/1/1/3/113553e1d14f526fd8aba1b6e163614db2fecd27.png)
By similar logic, 
. Multiplying, we get 
. is odd, the LHS is 
and the RHS is , a contradiction.
is even, and take both expressions modulo .![\[(1) \quad 2^n+65\equiv 1 +65\equiv 66\equiv 0 \pmod 3\]](http://latex.artofproblemsolving.com/4/4/f/44f160b0b70d3a66f88f280cabd0bc076a5f151c.png)
![\[(2) \quad 5^n-3^n\equiv 5^n\not\equiv 0\pmod 3\]](http://latex.artofproblemsolving.com/0/f/6/0f6c037779bacbe7449db71b2cba0b3465df2927.png)
Thus combining 
and 
yields a contradiction.
such that 
such that:![\[\left(\frac{5}{p}\right)\neq \left(\frac{3}{p}\right)\]](http://latex.artofproblemsolving.com/5/d/2/5d241b34ad30783c5de8fbcb6de45e40ff178b1a.png)
We get a contradiction as if and we have that:![\[5^n\equiv 3^n\pmod p\]](http://latex.artofproblemsolving.com/a/1/f/a1f8e5b7d99d04c32d412f29dea30d6f2b99bc63.png)
so we get:![\[\left(\frac{5^n}{p}\right)= \left(\frac{3^n}{p}\right)\]](http://latex.artofproblemsolving.com/0/f/6/0f6337e84dcb46a70644eabd54d30ef9f47b7536.png)
as is odd this means:![\[\left(\frac{5}{p}\right)= \left(\frac{3}{p}\right)\]](http://latex.artofproblemsolving.com/4/1/b/41bb06a290a68e7ce76b5183ef8dfa23e7988053.png)
Which is a contradiction. Now I will show such a exists. Using the jacobi symbol we get:![\[(1)\quad \left(\frac{5}{2^n+65}\right) = \left(\frac{2^n+65}{5}\right)=1\]](http://latex.artofproblemsolving.com/3/1/4/3141385a5fb64356364dd489947fdf3f77114d02.png)
![\[(2)\quad \left(\frac{3}{2^n+65}\right)=\left(\frac{2^n+65}{3}\right)=-1\]](http://latex.artofproblemsolving.com/c/4/9/c49353f476fb0d49d57ab606a13825a4fc97ce26.png)
These follow because is odd and 
. Now let 
.![\[\left(\frac{k}{2^n+65}\right)=\prod_{i=1}^{k}\left(\frac{k}{p_i}\right)^{\alpha_i}\]](http://latex.artofproblemsolving.com/8/3/c/83c6ac529022c2277ab1c07e22084fb7ba6fc01b.png)
If for all such 
we have that![\[\left(\frac{5}{p_i}\right)= \left(\frac{3}{p_i}\right)\]](http://latex.artofproblemsolving.com/f/1/5/f15a789243dd9c822887b108201c67308fb63628.png)
we get that:![\[\left(\frac{5}{2^n+65}\right)= \left(\frac{3}{2^n+65}\right)\]](http://latex.artofproblemsolving.com/2/1/1/2117e35d13e9430c29d5aed6f54cc6ab00206aca.png)
from the definition of the jacobi symbol. Thus this is a contradiction.
such that 
while 
.
for an integer 
.
.![\[ 5^n-3^n\equiv 0\pmod{p}\implies \left(\frac{5}{3}\right)^{2m}\equiv \frac{3}{5}\pmod{p},\]](http://latex.artofproblemsolving.com/e/4/c/e4ccd7a33996cc999516fb455b5b27b5fadff042.png)
where fractions are modular inverses. Hence, 
is a quadratic residue modulo 
by a simple application of quadratic reciprocity. Thus there are 
such that![\[ 2^{2m+1} + 5\equiv 2^n + 65\equiv 7^a11^b17^c(-1)^d\pmod{60}.\]](http://latex.artofproblemsolving.com/2/8/b/28b4319321add23d54f10ab4186b1924c63bdefc.png)
Doing some bashing (it’s not that bad; note that the orders of 
are 
)![\[2^{2m+1} + 5\in\{1, 59, 43, 17, 49, 11, 7, 53\}\pmod{60}.\]](http://latex.artofproblemsolving.com/4/6/5/4650f1cfd1d69df9f5c6a57f072b26236cc20c87.png)
Hence, 
.
are 
,
,
.
is necessary. But it is clear that 
,
and obviously 
.
.
and 
are not quadratic residues modulo 
.
and 
,
,
for which 
.
,
.
,
,
,
be a prime divisor of 
because 
so 
implying that 
since 
.
as well, this implies that 
as well, where 
denotes Legendre symbol. Now, assume for the sake of contradiction that 
However, since ![\begin{align*}
1 &= \left(\frac{1}{p}\right) \\
&= \left(\frac{(5/3)^n}{p}\right) \\
&= \left[\left(\frac{5/3}{p}\right)\right]^n \\
&= (-1)^n \\
&= -1,
\end{align*}](http://latex.artofproblemsolving.com/9/0/d/90d83c9e2d864026414cae59f8dcae5983ed1d9c.png)
a contradiction. Thus, we must have that 
,
.
is a QR iff 
is (this follows since 
)
Thus, we have four cases. Note that 
if 
,
if 
(note that we have assumed that 
)
if 
,
(we have shown 
if 
and 
(we have shown 
.
,
from the above characterizations.
.
from the above characterizations.
.
,
types of odd primes 
such primes of the 
t
so we have that 
so it follows that 
is even. Since 
so we have that 
so 
.
so we have that 
so 
implying that 
is odd. However, since 
is even. Since 
is also even, it follows that 
is even as well, a contradiction.
,
,
.
.
.
,
clearly and 
by 
Now if 
then 
with 
Now we must have 
which is equivalent by QR to 
But 
for odd 
and we can check 
contradiction.
From here on, our solution will consider 
which implies 
or, using Jacobi's notation:
We can easily prove each of there: (1) is from 
= (-1), multiplicity (or rather, power-icity) and 
.
,
.
.![\[
\left(\frac{15}{2^n+65}\right)=\left(\frac{3}{2^n+65}\right) \left(\frac{5}{2^n+65}\right)=\left(\frac{2^n+65}{3}\right) \left(\frac{2^n+65}{5}\right)=\left(\frac{2^n+2}{3}\right) \left(\frac{2^n}{5}\right)=(-1)(1)=-1
\]](http://latex.artofproblemsolving.com/7/3/1/731cf74fac35f050e8a75de4b1ef6a0a0c6052cc.png)