Loading [MathJax]/jax/output/HTML-CSS/jax.js

User Tools

Site Tools


pow:problem5f21

Problem 5 (due Monday, November 8)

We call a positive integer N prosperous if ϕ(N)+σ(N)=2(N+1)  and  ϕ(N)σ(N)=(N5)(N+3). Knowing that both N and N504 are prosperous, find N.

Remark. Here ϕ is the Euler function and σ is the sum of divisors:

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

σ(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 ϕ or σ.

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