0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ $23{}{}{}{}{}{}$ $\endgroup$ – TMM May 31 '13 at 13:11
  • $\begingroup$ One method involves the Chinese Remainder Theorem, which see. $\endgroup$ – Gerry Myerson May 31 '13 at 13:14
  • $\begingroup$ Could you be more specific ? $\endgroup$ – itamar May 31 '13 at 13:45
  • $\begingroup$ @GerryMyerson , how could I use the chinese remainder theorem while 8 and 12 are not coprime ? $\endgroup$ – itamar May 31 '13 at 13:45
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson May 31 '13 at 23:05
1
$\begingroup$

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)$$

$\endgroup$
0
$\begingroup$

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).$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.