Differences

This shows you the differences between two versions of the page.

--- pow:problem5f21 [2021/11/08 03:53] – created mazur
+++ pow:problem5f21 [2021/11/09 04:42] (current) – mazur
@@ Line 1: / Line 1: @@
+<box 85% round orange| 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$.
+</box>
+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 {{:pow:2021fproblem5.pdf|Solution}}.