Question continuing from mrW1 post on p^2 mod n≡1. Find a number n such that for all m<n such that HCF(m,n)=1 m^2 mod n =1 e.g. for 12 possible value of m are 1,5,7,11.


Question and Answers Forum

All Questions Topic List
Number Theory Questions
Previous in All Question Next in All Question
Previous in Number Theory Next in Number Theory
Question Number 13733 by prakash jain last updated on 22/May/17

$Question continuing from$ $mrW 1 post on p^{2} \mod n \equiv 1 .$ $Find a number n such that$ $for all m < n such that HCF (m, n) = 1$ $m^{2} \mod n = 1$ $e . g . for 12 possible value of m$ $are 1, 5, 7, 11 .$
Commented by prakash jain last updated on 22/May/17

$This will be sufficient condition$ $for p^{2} \mod n = 1 .$ $Can be considered necessary if we$ $assume that for m < n where$ $HCF (m, n) = 1 there exists at$ $least one prime of the form$ $l n + m where (l, m, n) are natural numbers .$
Commented by mrW1 last updated on 23/May/17

$F o r m s u c h t h a t a l l p r i m e n u m b e r s$ $c a n b e e x p r e s s e d a s p = m k \pm 1, I t h i n k$ $t h e r e a r e o n l y f o l l o w i n g p o s s i b i l i t i e s :$ $m = 2 : p = 2 k \pm 1 \Rightarrow n = 4$ $m = 4 : p = 4 k \pm 1 \Rightarrow n = 8$ $m = 6 : p = 6 k \pm 1 \Rightarrow n = 12$
Commented by prakash jain last updated on 23/May/17

$Yes . For any number n we can$ $express all primes as$ $m n + k where HCF (k, n) = 1, k < n$ ${(m n + k)}^{2} \mod n = k^{2} \mod n$ $n = 12 \Rightarrow k = 1, 5, 7, 11$ $5^{2} \equiv 1 (\mod 12)$ $7^{2} \equiv 1 (\mod 12)$ $Now the question is to find n where$ $k^{2} \mod n = 1 (HCF (k, n) = 1, k < n)$ $(or to prove that no such n exist) .$
Commented by prakash jain last updated on 23/May/17

$continuing$ $k^{2} \mod n = 1$ $k^{2} = m n + 1$ $k^{2} - 1 = m n$ $(k - 1) (k + 1) = m n$
Terms of Service
Privacy Policy
Contact: info@tinkutara.com

Question and Answers Forum