Determine all integers $n \geq 2$, satisfying $$n=a^2+b^2,$$where $a$ is the smallest divisor of $n$ different from $1$ and $b$ is an arbitrary divisor of $n$. Proposed by Walther Janous
Problem
Source: Austrian Mathematics Olympiad Regional Competition (Qualifying Round) 2017, Problem 4
Tags: number theory, Sum of Squares, Divisors, Divisibility
12.06.2018 05:39
Can the arbitrary divisor can be chosen as the smallest divisor?
12.06.2018 05:41
^ Why not?
12.06.2018 06:03
Notice both sides of the equation are divisible by $b$. This means $b$ divides $a^2$. But $a$ is simply the smallest prime divisor of $n$, so $b=1$ or $b=a$ or $b=a^2$. $b=1$ fails. Taking $b=a$, we have $n=2a^2$, so $2$ divides $n$, and as 2 is the smallest possible value that a divisor can have, we conclude $a=2$, giving us $n=8=2^2+2^2$. Taking $b=a^2$, we have $n=a^2(1+a^2)$. But one notices that since $a$ is prime, if $a>2$, then $(1+a^2)$ must be even, meaning n is even, meaning it is divisible by 2, contradicting $a$'s minimality. Thus $a=2$. This gives us one more solution, $n=20=2^2+4^2$. So, $n=8$ and $n=20$ are the only solutions.
12.06.2018 06:11
@above Please explain this! Taking $b=a^2$, we have $n=a^2(1+a^2)$. But one notices that since $a$ is prime, if $a>2$, then $(1+a^2)$ must be even, meaning n is even, meaning it is divisible by 2, contradicting $a$'s minimality.
12.06.2018 06:15
IMO2019 wrote: @above Please explain this! Taking $b=a^2$, we have $n=a^2(1+a^2)$. But one notices that since $a$ is prime, if $a>2$, then $(1+a^2)$ must be even, meaning n is even, meaning it is divisible by 2, contradicting $a$'s minimality. "Contradicting a's minimality"="contradicting the fact that a is the smallest prime that divides n". We know $a$ is the smallest prime that divides $n$, yes? But if $a>2$ then $a^2+1$ would be even, because $a$ is odd. So $n$ is divisible by $2$. But $2$ is smaller than $a$! So this contradicts the definition of $a$, because nothing can be smaller! So the case fails!
12.06.2018 06:18
Oh thanks! Nice solution. I am so stupid.
12.06.2018 10:47
See my solution from here
12.06.2018 10:49
Oh, thanks for the link! I am locking this topic.