User Tools

Site Tools


Problem 5 (due Monday, November 8)

We call a positive integer $N$ prosperous if \[ \phi(N)+\sigma(N)=2(N+1) \ \ \text{and}\ \ \phi(N)\sigma(N)= (N-5)(N+3).\] Knowing that both $N$ and $N-504$ are prosperous, find $N$.

Remark. Here $\phi$ is the Euler function and $\sigma$ is the sum of divisors:

$\phi(N) =$ the number of positive integers which are relatively prime to $N$ and do not exceed $N$,

$\sigma(N) =$ the sum of all positive divisors of $N$.

These functions are studied in elementary number theory (a topic of Math 407). They both are so called multiplicative functions: for any two relatively prime integers $M,N$ we have $f(MN)=f(M)f(N)$, where $f$ is either $\phi$ or $\sigma$.

We received solutions from Ashton Keith, Maxwell T Meyers, and Pluto Wang. Ashton provides a short solution which requires some direct computations at the end. Maxwell shows that the first condition in the definition of a prosperous number holds for $M$ if and only if $M=pq$ is a product of two distinct prime numbers. From this he concludes that $M$ is prosperous if and only if $M=p(p+4)$ where both $p$ and $p+4$ are prime numbers. From this he shows that $N=2021$ is the only solution to the problem. Pluto has a partial solution, which proves what Maxwell showed but only when $M$ is a product of distinct prime numbers (i.e. $M$ is square-free). Maxwell's solution is the same as my original solution. However, I later realized that the second condition in the definition of the prosperous number implies the first one. For more details see the following link Solution.

pow/problem5f21.txt · Last modified: 2021/11/08 23:42 by mazur