A positive integer n is called primary divisor if for every positive divisor $d$ of $n$ at least one of the numbers $d - 1$ and $d + 1$ is prime. For example, $8$ is divisor primary, because its positive divisors $1$, $2$, $4$, and $8$ each differ by $1$ from a prime number ($2$, $3$, $5$, and $7$, respectively), while $9$ is not divisor primary, because the divisor $9$ does not differ by $1$ from a prime number (both $8$ and $10$ are composite). Determine the largest primary divisor number.
Problem
Source: Dutch NMO 2022 p1
Tags: number theory, divisor
18.11.2022 00:36
Lemma: Every odd number $q$ $\ge 5$ is not primary divisor. Proof: $q$ is a divisor of itself, so either $q+1$ or $q-1$ has to be prime, which they clearly aren't as they are even and bigger than $2$. If number $q$ now divides a number $k$, then this automatically implies $k$ isn't a primary divisor as $q$ isn't one. Because of our lemma and previous statement, we only have to consider numbers with prime divisors $2$ and $3$. Notice that $v_3(n) \le 1$ as $9$ isn't a primary divisor as nor $8$ or $10$ is prime. Also, $v_2(n) \le 5$ as for $64$, we have that $63$ and $31$ aren't prime. The only primary divisors are $1,2,3,4,6,8,12,16,24,32,48$
27.08.2023 21:13
straight wrote: Lemma: Every odd number $q$ $\ge 5$ is not primary divisor. Proof: $q$ is a divisor of itself, so either $q+1$ or $q-1$ has to be prime, which they clearly aren't as they are even and bigger than $2$. If number $q$ now divides a number $k$, then this automatically implies $k$ isn't a primary divisor as $q$ isn't one. Because of our lemma and previous statement, we only have to consider numbers with prime divisors $2$ and $3$. Notice that $v_3(n) \le 1$ as $9$ isn't a primary divisor as nor $8$ or $10$ is prime. Also, $v_2(n) \le 5$ as for $64$, we have that $63$ and $31$ aren't prime. The only primary divisors are $1,2,3,4,6,8,12,16,24,32,48$ First: 31 is prime Second: To determine the largest prime divisor number we have that since 64 does not meet and 9 neither, then the maximum is 32 ∗ 3 which is 96 and meets 97 which is prime