Hello Codeforces,
Recently I was trying to make a number theory problem, I haven't framed the entire question yet but the core part goes something like this $$$-$$$ Given an integer $$$a$$$, find an integer $$$b$$$ ($$$ \le a $$$) such that $$$gcd(a,b)$$$ $$$+$$$ $$$lcm(a,b)$$$ is a prime number.
The condition $$$gcd(a,b)$$$ $$$+$$$ $$$lcm(a,b)$$$ is a prime number boils down to $$$gcd(a,b) = 1$$$ and $$$a \cdot b + 1$$$ is a prime where $$$b \le a$$$.
I tried brute-forcing $$$b$$$ by fixing $$$a$$$ and I found that there exists such $$$b$$$ for all $$$1 \le a \le 10^5$$$. However, I am not sure whether there exists such $$$b$$$ for all $$$a$$$. Does anyone have a formal or intuitive proof why this is happening and is there any approach to find $$$b$$$ given $$$a$$$ ?
Auto comment: topic has been updated by wakanda-forever (previous revision, new revision, compare).
This is kind of guaranteed by Dirichlet's Theorem
However using that theorem the condition $$$b \leq a$$$ isn't guaranteed. It still seems very likely to be true for all $$$a$$$, as it would be a very unexpected coincidence for all $$$a$$$ choices of $$$b$$$ value to 'skip' being primes, as primes are pretty dense.
Linnik's theorem and GRH currently give an unconditional bound for the least prime (p) satisfying
for any coprime pair (a,b) in the form
Under GRH, one can take (x < 3), while unconditionally (by Linnik’s theorem) one has (x <= 5). If someone were ever to prove a bound with $$$ x \lt 1 $$$ , that would be a major breakthrough in number theory.
Don't let this guy be a problem setter on div. 2 please
well well well. I guess we have to skip the div 2 on september 9th then! maybe a similar problem to this might show up on it (the timeline fits well)...
R.I.P
I think there is something to do with phi function