I'm trying to prove a graph theoretic lemma for my research; I need to construct graph homomorphisms between some delicately defined graphs.

I believe I can do this if (and maybe only if) I can find solutions to the following.

For arbitrarily large pairs of coprime $p$, $q$, find coprime $p',q'\gg p,q$, along with integers $n,n_{ta},n_{tb},n_{la},n_{lb}$ such that

  • $q'n_{ta}-p'n_{la}=nq$;
  • $q'n_{tb}-p'n_{lb}=np$;
  • $p|n_{ta}|+q|n_{tb}|\ll p'$, and further, $pn_{ta}+qn_{tb}=1\mod 2$;
  • $p|n_{la}|+q|n_{lb}|\ll q'$, and further, $pn_{la}+qn_{lb}=1\mod 2$.

If $\gg$ is too vague, we can take $x\gg y$ if $x> 1000y$; that should more than suffice.

I have so far failed to find even one $p,q$ for which the above holds, let alone arbitrarily large $p,q$. My methods are crude, however; I'm not experienced in number theory.

My questions:

  1. Does anyone have a quick solution, partial solution, or proof in the negative?
  2. Failing that (likely), how difficult a problem is this?
  3. Is there a field (or better, textbook or wikipedia page) that will give me techniques to solve such problems if I encounter them in the future?
  4. Are such problems amenable to software techniques? Are there software packages existing that assist with solving such problems?

Naturally, the risk of having made a mistake in specifying my constraints is high, so a general literacy in dealing with such constraints is more useful than a specific solution.



You must log in to answer this question.

Browse other questions tagged .