Prove that there exist infinitely many positive integers which cannot be written in form $a^{d(a)}+b^{d(b)}$ for some positive integers $a$ and $b$ For positive integer $d(a)$ denotes number of positive divisors of $a$ Proposed by Borna Vukorepa
Problem
Source: European Mathematical Cup 2014, Senior Division, P1
Tags: modular arithmetic, number theory, prime factorization, number theory unsolved
professordad
15.12.2014 06:19
All integers congruent to $3 \pmod{4}$ cannot be expressed this way. We prove this by showing that each $a^{d(a)}$ is a perfect square and taking mod 4. $a^{d(a)}$ is a perfect square if $d(a)$ is even. If $d(a)$ is odd, then the exponents in $a$'s prime factorization must all be even, so $a$ is a perfect square and $a^{d(a)}$ is a perfect square.
ZetaX
15.12.2014 06:46
Lets make it a bit more difficult: try the same problem with $a^{d(b)}+b^{d(a)}$.
Submathematics
15.12.2014 22:33
Zetax Can show the solution of your problem? I am unable to do it.
esi
16.12.2014 08:59
for the second problem $p^2$ works when $p=4k+3$ if $a,b\neq x^2$ then d(a) and d(b) is perfect square. so for some m,n $m^2+n^2=p^2$ ,$m^2=(p-n)(p+n)$,but $n,m$ are positive so $\gcd (p-n,p+n)=1,2$ in both cases 2p or p is sum two perfect squares so $p=a^2+b^2$ contradiction if $a=x^2, b=y^2$ we have another time $m^2+n^2=p^2$ if $a=x^2, b\neq y^2$ we have $n^2 + b^{2m+1}=p^2$ for some m,n $(p-n)(p+n)=b^{2m+1}$ but n is positive so $\gcd (p-n,p+n)=1,2$ in both cases $p=k^{2m+1} + s^{2m+1} or 2p =k^{2m+1}+ s^{2m+1}$ for some k,s. also we know that $2m+1=d(x^2)>1$ by some little work the first equation gives us k=s=1 and p=2 (contradiction) and the second one k=s=p=1(contradiction)
NgoNgang
16.12.2014 21:25
Someone has the junior version of test problems for this same competition?