# 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. – Somos Oct 11 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. – a.. Oct 11 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? – Daniel Lichtblau Oct 12 at 13:40
• @DanielLichtblau Exactly. It appears mathematica is not very straightforward with procedural programming with loops. – a.. Oct 12 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. – Daniel Lichtblau Oct 12 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? – a.. Oct 12 at 20:14
• With "PrimeQ[au + bv] || GCD[ab, uv] =!= 1" seems address all of 1,2,3 and 4. Correct? – a.. Oct 12 at 20:14
• Yes, all four are addressed – Daniel Lichtblau Oct 12 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? – a.. Oct 13 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. – Daniel Lichtblau Oct 13 at 21:35