6
$\begingroup$

How many solutions are there for $a^{2014} +2015\cdot b! = 2014^{2015}$, with $a,b$ positive integers?

This is another contest problem that I got from my friend.

Can anybody help me find the answer? Or give me a hint to solve this problem?

Thanks

$\endgroup$
1
  • $\begingroup$ Could you provide more detail about what contest it is from? $\endgroup$
    – JRN
    Mar 17, 2015 at 4:21

4 Answers 4

6
$\begingroup$

Taking this equation mod $2015$ yields $a^{2014} \equiv -1 \pmod{2015}$.

Since $2015 = 5 \cdot 13 \cdot 31$, we get the following:

$a^{2014} \equiv -1 \pmod{5}$

$a^{2014} \equiv -1 \pmod{13}$

$a^{2014} \equiv -1 \pmod{31}$

By Fermat's Little Theorem, $a^{31} \equiv a \pmod{31}$. Hence, $a^4 \equiv a^{2014} \equiv -1 \pmod{31}$.

We can check that $-1$ is not a quadratic residue $\pmod{31}$. Thus, there is no residue $a^2$ such that $(a^2)^2 = a^4 \equiv -1 \pmod{31}$. Therefore, there are no solutions to the original equation.

$\endgroup$
7
  • $\begingroup$ What is the useful for us to check that -1 isn't a quadratic residue mod 31? $\endgroup$
    – akusaja
    Jun 15, 2014 at 19:07
  • $\begingroup$ Are you asking why it is useful to check that -1 isn't a quadratic residue mod 31, or are you asking how we can check that -1 isn't a quadratic residue mod 31? $\endgroup$
    – JimmyK4542
    Jun 15, 2014 at 19:13
  • $\begingroup$ Yes, I'm asking about how important for us to check that -1 isn't a quadratic residue mod 31. I don't know why you attack this problem with this way. Thanks $\endgroup$
    – akusaja
    Jun 15, 2014 at 19:16
  • $\begingroup$ I have shown that if $(a,b)$ is a solution to the original equation, then $a^4 \equiv -1 \pmod{31}$. By checking that $-1$ is not a quadratic residue $\pmod{31}$, we see that no integer $a$ satisfies $a^4 \equiv -1 \pmod{31}$. Therefore, there cannot be any solutions $(a,b)$ to the original equation. $\endgroup$
    – JimmyK4542
    Jun 15, 2014 at 19:21
  • $\begingroup$ Oh, I just knew that you shown that this problem didn't have any integer solution. So, your way is only to prove that there are no solutions for this problem? Thanks $\endgroup$
    – akusaja
    Jun 15, 2014 at 19:24
1
$\begingroup$

Here's a line of attack that leaves you the task of checking only finitely many cases. The idea is to check divisibility by powers of two. I use the notation $\nu(m)$ to denote the exponent of the highest power of two that divides a positive integer $m$, so e.g. $\nu(80)=\nu(16\cdot5)=4$, because $2^4=16$.

You have probably seen (or can prove it as an exercise) that $$ \nu(m!)=\sum_{i=1}^{\lceil \log_2m\rceil} \lfloor\frac m {2^i}\rfloor.\qquad(*) $$ Also $\nu(mn)=\nu(m)+\nu(n)$, and consequently $\nu(m^n)=n\nu(m)$. Furthermore, if $\nu(a)\neq\nu(b)$ then $\nu(a+b)=\min\{\nu(a),\nu(b)\}$. This latter property is known as non-Archimedean triangle inequality. Let's call it NATI for short.

Here we see that $\nu(2014^{2015})=2015\cdot\nu(2014)=2015$ because $2014$ is even, but not divisibile by four.

Let us first consider the possibility that $a$ is odd. Then so is $a^{2014}$, so $2015\cdot b!$ must be odd. This is possible only, if $b!$ is odd, so we must have $b=0$ or $b=1$ for otherwise $b!$ is even. Check, whether there is matching $a$.

Let us then turn our attention to the possibility that $a$ is even. We first assume that $a$ is not divisible by four or, equivalently, that $\nu(a)=1$. In that case $\nu(a^{2014})=2014$. Because $\nu(2014^{2015})=2015$, NATI restricts the choice of $b$ to those numbers that have $2014=\nu(2015\cdot b!)=\nu(b!)$. Formula $(*)$ comes in handy. I give you the extra bit $\nu(2022!)=2014$. There are very few other possibilities for $b$, because $\nu(b!)$ is a (non-strictly) increasing function of $b$.

Finally, if $\nu(a)>1$, then $\nu(a^{2014})\ge2\cdot2014$, which is greater than $2015$. In this cases NATI forces $\nu(b!)=2015$. This again severely limits the possibilities for $b$.

$\endgroup$
2
  • $\begingroup$ Altogether this leaves four possibilities for $b$: $0,1,2022,2023$. Armed with a CAS it is easy to check that none of these work. G.T.R can eliminate the big ones. JimmyK (+1) does everything very differently. $\endgroup$ Jun 15, 2014 at 19:02
  • $\begingroup$ is it possible for us to find the solution only by hand? it seems that the number is very big for us. Thanks $\endgroup$
    – akusaja
    Jun 15, 2014 at 19:11
1
$\begingroup$

Not the whole solution, but enough to get going.

We have that $\displaystyle a^{2014}+b!\equiv 0 \pmod{2014}$

  • If $b\geq 53$, then $\displaystyle a^{2014}\equiv 0 \pmod{2014}$.

Since $2014=2\times19\times53$, this implies $\displaystyle a\equiv 0 \pmod{2014}$

Hence $a=2014k$ for some positive $k$

Plugging this in yields $\displaystyle 2014^{2014}k^{2014}+2015 b!=2014^{2015}$

Hence $2014^{2014}(2014-k^{2014})=2015 b!$

The RHS being positive, so is the LHS, and thefore $2014\geq k^{2014}$, which forces $k=1$

Therefore $a=2014$. Furthermore, $2014^{2014}(2013)=2015 b!$ is clearly a contradiction.

  • Thus, $b\leq 52$
$\endgroup$
6
  • $\begingroup$ @JyrkiLahtonen major failure in my reasoning. It's fixed now but less interesting. Does your answer give a better bound on $b$ ? $\endgroup$ Jun 15, 2014 at 18:54
  • $\begingroup$ My line leaves four possible values for $b$. Two of which are $b=0$ and $b=1$. The OP asked for hints only, so I didn't check any of those. The other two are $>53$, so your argument helps :-) $\endgroup$ Jun 15, 2014 at 18:56
  • $\begingroup$ @G.T.R, must we check all possibilities for b<= 52, or we can simply say that the number of solutions for this problem is 53? thanks $\endgroup$
    – akusaja
    Jun 15, 2014 at 19:03
  • $\begingroup$ @akusaja See what Jyrki has written in his comment "Altogether this leaves four possibilities for $b: 0,1,2022,2023$. Armed with a CAS it is easy to check that none of these work. G.T.R can eliminate the big ones. JimmyK (+1) does everything very differently. " $\endgroup$ Jun 15, 2014 at 19:06
  • 1
    $\begingroup$ @akusaja yes, there is no solution. $\endgroup$ Jun 15, 2014 at 19:23
1
$\begingroup$

Hint $ $ If $\,n\,$ is odd, and $\ a^{n-1}\! + n b = (n-1)^{2j+1} $ then every prime $\,p\,$ dividing $\,n\,$ is $\,\equiv 1\pmod 4 $ since $\ n\!-\!1 = 2k,\,$ so $\, {\rm mod}\ p\!:\ (a^k)^2 \equiv\, -1,\ $ so by Euler or reciprocity, $ $ we infer $\ p\equiv 1\pmod 4$

$\endgroup$
6
  • $\begingroup$ By seeing Jimmy's solution, is your hint convinced us to conclude that there is no solution for this problem? Thanks $\endgroup$
    – akusaja
    Jun 16, 2014 at 15:52
  • $\begingroup$ @akusaja $ $ Does $\ n = 2015 = 5\cdot 13\cdot 31\ $ have every prime divisor $\equiv 1\pmod 4\,?\ \ $ $\endgroup$ Jun 16, 2014 at 16:08
  • $\begingroup$ no, 2015 didn't have any prime divisor, such that ≡ 1(mod 4) because it's didn't fit with Euler's theorem. From here, can we say that because every prime divisor of 2015 isn't ≡ 1(mod 4), so this problem has no solution? Thanks $\endgroup$
    – akusaja
    Jun 16, 2014 at 16:15
  • $\begingroup$ @akusaja $2015$ does not have every prime divisor $\,\equiv 1\pmod 4\,$ since $\,31\equiv 3.\,$ You will encounter similar criteria for other Diophantine equations, so it is instructive to bring this innate structure to the foreground, to help you more easily recognize analogous instances in the future. $\endgroup$ Jun 16, 2014 at 16:23
  • 1
    $\begingroup$ @akusaja $ $ Above, since $\,n=2015\,$ is odd, $\ n -1\,$ is even, $ $ therefore $\,n-1 = 2k.\,$ Now reduce $\,a^{n-1}\!+\color{#c00}nb\, =\, (\color{#0a0}{n\!-\!1})^{2j+1}\,$ mod $\,p,\,$ where $\,p\mid n\,\Rightarrow\,\color{#c00}{n\equiv 0}\,\Rightarrow\,\color{#0a0}{n\!-\!1\equiv -1}.\, $ Therefore, mod $\,p\,$ we get $\ a^{2k}\, +\,\ \color{#c00}0\ \ \equiv\ \ (\color{#0a0}{-1})^{2j+1}\equiv\, -1,\ $ thus $\ {-}1\,\equiv\, (a^k)^2\,$ is a square mod $\,p,\,$ hence $\,p\equiv 1\pmod{4}\quad $ $\endgroup$ Jun 16, 2014 at 16:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .