# Smallest number $n$ $=$ $ak+b$ with properties of Euler's totient

Given two relatively prime integers $a$ and $b$, find the smallest integer of the form $ak+b$ $=$ $n$ $>$ $2$ such that $\gcd(φ(n), n)$ $=$ $1$, and least one divisor $d | n$, $d > 1$, the $\gcd(d-1, n-1)$ $<=$ $2$. Let $E(a, b)$ denote this exact smallest integer $n$ with these properties for $a$ and $b$.

With $a = 1$, $b = 0$, $E(a, b) = 15$ because $\gcd(φ(15), 15) = 1$, and $3 | 15$, $\gcd(2, 14) <= 2$

With $a = 12, b = 1$, $E(a, b) = 517$ because $\gcd(φ(517), 517) = 1$, and $11 | 517$, $\gcd(10, 516) <= 2$

Is anyone able to prove that $(12, 1)$ is the smallest and only relatively prime $a, b$ pair with both $(a, b)$ $<= 12$ such that $E(a, b)$ $=<$ $517$? Also, what wouldd be the smallest expected $a, b$ relatively prime pair such that $E(a, b) => 100000$? If anyone knows of small $a, b$ relatively prime pairs with $E(a, b)$ an extraordinary large value, please mention them. Thanks for help.

• Some questions: (1) Presumably, you require $a > 0$, $b \ge 0$. Yes? (2) The divisor $d$ is required to be a proper divisor of $n$ (i.e., $d \ne n$). Yes? (3) What do you mean by the "smallest" pair $(a,b)$? Smallest with respect to what ordering? – quasi Mar 5 '17 at 5:07
• @quasi (1) yes. (2) yes. (3) smallest values of $a$ first, then values of $0 < b < a$. – J. Linne Mar 5 '17 at 6:22

## 1 Answer

I don't really see any structure that would allow "by-hand" solutions for large values of the variables.

Using a Maple program, a brute-force search yields the following results relating to the questions you asked:

• $E(a,b) < 517$ for all $(a,b)$ with $a,b < 12$.
• The pair $(a,b) = (219,4)$ is the smallest pair such that $E(a,b) \ge 10000$.