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

Question

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.

Answer 1

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$.