# 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. 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. 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? Oct 12, 2020 at 13:40
• @DanielLichtblau Exactly. It appears mathematica is not very straightforward with procedural programming with loops. 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. 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, Continue[]];
{u, v} = {1, -1}*egcd[];
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 Table[primeVectors[1000, 15], 10] (* Out= {{{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? Oct 12, 2020 at 20:14
• With "PrimeQ[au + bv] || GCD[ab, uv] =!= 1" seems address all of 1,2,3 and 4. Correct? Oct 12, 2020 at 20:14
• Yes, all four are addressed 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? 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. Oct 13, 2020 at 21:35