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$ ?
↵
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$ ?
