1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – quasi Mar 5 '17 at 5:07
  • $\begingroup$ @quasi (1) yes. (2) yes. (3) smallest values of $a$ first, then values of $0 < b < a$. $\endgroup$ – J. Linne Mar 5 '17 at 6:22
1
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.