# Solving A Linear Congruential System

I need to find a prime p which makes: $p\equiv {\pm1}\text{ (mod }8)$ and $p\equiv {\pm1}\text{ (mod }12)$

How could I find such $p$? Is there any specified method I can use? I'd be grateful if anyone could point me to the solution. Thanks in advance!

• $23{}{}{}{}{}{}$ – TMM May 31 '13 at 13:11
• One method involves the Chinese Remainder Theorem, which see. – Gerry Myerson May 31 '13 at 13:14
• Could you be more specific ? – itamar May 31 '13 at 13:45
• @GerryMyerson , how could I use the chinese remainder theorem while 8 and 12 are not coprime ? – itamar May 31 '13 at 13:45
• The CRT says $x\equiv a\pmod m$ and $x\equiv b\pmod n$ have a simultaneous solution provided $a\equiv b\pmod{\gcd(m,n)}$. See en.wikipedia.org/wiki/Chinese_remainder_theorem or any intro Number Theory textbook. – Gerry Myerson May 31 '13 at 23:05

Iff:$$q\equiv {a}\text{ (mod }lcm(n,m))$$ then $$q\equiv {a}\text{ (mod }n)$$ and: $$q\equiv {a}\text{ (mod }m)$$ so it suffices to solve $q\equiv {a}\text{ (mod }lcm(n,m))$ and then check the primality of $q$. So if we take: $$n=8,m=12,a=-1$$ we try to solve: $$q\equiv {-1}\text{ (mod }lcm(8,12)=24)$$ which is equivalent to: $$q\equiv {23}\text{ (mod }lcm(8,12)=24)$$ and we're in luck that $q=23$ is a simple solution; i.e it is a prime. If instead we take: $$q\equiv {1}\text{ (mod }lcm(8,12)=24)$$ the solutions will be: $$q=1,24+1, 2\times24+1,3\times24+1...$$ We can then test for primality; I use maple with the comand "$\text{isprime}(1+24k)$", flick through $k$ and get "true" for $k=3$, so: $$p=q=1+24\times3=73$$ is a prime that solves: $$p\equiv {1}\text{ (mod }8)$$ $$p\equiv {1}\text{ (mod }12)$$
If $\ \color{#c00}{4\mid m,n}\$ then $\ x\equiv \pm1\pmod m\,$ and $\!\!\pmod n$ $\!\iff\! x\equiv \pm1\pmod{\ell},\,\ \ell = {\rm lcm}(m,n).$
Indeed, $\ m,n\mid x\!-\!1 \iff {\rm lcm}(m,n)\mid x\!-\!1,\$ and similarly for $\ x\!+\!1.$
Else $\ m\mid x\!-\!1,\,\ n\mid x\!+\!1\,\smash[t]{\stackrel{\large\color{#c00}{ 4\,\mid\, m,n}}\Rightarrow}\, 4\mid x\!-\!1,x\!+\!1\,\Rightarrow\, 4\mid x\!+\!1\!-\!(x\!-\!1) = 2,\,$ contradiction, or
else $\,\ m\mid x\!+\!1,\,\ n\mid x\!-\!1,\$ which, similarly, yields a contradiction.
Thus in your case $\,m,n = 8,12\,$ case we get $\ p = x\equiv \pm1\pmod{24},\,$ by $\,24 = {\rm lcm}(8,12).$