Question-continuing-from-mrW1-post-on-p-2-mod-n-1-Find-a-number-n-such-that-for-all-m-lt-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 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