# How to write this simple task of unimodular prime search in mathematica?

For testing a particular algorithm I found mathematica is the best way as it has all the tools I need. I am stuck in a number theory part and since I am not an expert in mathematica I do not know how to write a code that seemingly involves loops. I want to pick random integers $$a,b$$ in interval $$[T,2T]$$ at $$T>0$$ and obtain $$u,v\in\mathbb Z$$ such that

1. $$au-bv=1$$ (Euclidean algorithm)

2. $$au+bv$$ is a prime

3. $$GCD(ab,uv)=1$$

4. $$0

holds.

Is there simple enough code to do this?

It would help me to have 5. $$a,b,u,v$$ are all prime integers.

• You realize there will very likely be an infinite number of such $u,v$ pairs? Or is just one instance enough? I suggest using the FindInstance[] function without any loops. Commented Oct 11, 2020 at 18:30
• There are so many conditions. If I know correct a and b find instance will work. Or else it is quadratic diophantine. Commented Oct 11, 2020 at 22:22
• I think this is misworded. In general such u,v need not exist. Are you wanting code that will keep picking random a,b until you get a pair for which they do exist? Commented Oct 12, 2020 at 13:40
• @DanielLichtblau Exactly. It appears mathematica is not very straightforward with procedural programming with loops. Commented Oct 12, 2020 at 14:17
• (1) The coding is straightforward. One just needs to know the parameters of the problem. That is, are all of a,b,u,v sought or just, as it was worded, u and v? (2) Loops, should you wish to use them explicitly, can be accomplished with any of For, Do, and While. Same as in other languages. Commented Oct 12, 2020 at 14:44

primeVectors[max_, tries_] := Catch[Module[
{a, b, done = False, tt = 0, u, v, egcd},
While[! done && tt < tries,
tt++;
{a, b} = RandomInteger[{2, max}, 2];
egcd = ExtendedGCD[a, b];
If[egcd[[1]] =!= 1, Continue[]];
{u, v} = {1, -1}*egcd[[2]];
If[u < 0,
{u, v} = {u, v} + {b, -a}; If[u < 0, Continue[]]];
If[(! PrimeQ[a*u + b*v] || GCD[a*b, u*v] =!= 1), Continue[],
Throw[{{a, b}, {u, v}}]]
];
$Failed ]]  examples: SeedRandom[1234] Table[primeVectors[1000, 15], 10] (* Out[2247]= {{{899, 664}, {243, 329}}, $$Failed, {{544, 695}, {359, -807}},$$Failed,$Failed, {{215,
571}, {409, -276}}, {{79, 347}, {123, 28}}, {{313, 555}, {172,
97}}, {{581, 155}, {151, -596}}, {{395, 313}, {42, 53}}} 7} *)

• This is a bit complicated as I am seeing for first time. So this address 1,2 and 4? Commented Oct 12, 2020 at 20:14
• With "PrimeQ[au + bv] || GCD[ab, uv] =!= 1" seems address all of 1,2,3 and 4. Correct? Commented Oct 12, 2020 at 20:14
• Yes, all four are addressed Commented Oct 12, 2020 at 20:31
• May I ask how $a,b$ in $[T,2T]$ is guaranteed? I need a, b} = {a,b}=RandomInteger[{T,2T},2] correct? Commented Oct 13, 2020 at 20:22
• I used max for your T. So they are selected to be less. If you want them in [T,2T] then that random generation needs to be modified slightly. Commented Oct 13, 2020 at 21:35