Pari/A123239

[devarajkandadai]

This sequence: impossible prime factors of (3^n-2).In pari to test whether 13 is an impossible prime factor of (3^n-2) my code: {is(n)=Mod(3^13)^n==2}; for(n=1,12,print(is(n))).
Is there s shorter cut?

[LaurV]

Originally Posted by devarajkandadai

Is there s shorter cut?

yes, you will only need to test for 3^2 (mod 13), and 3^3 (mod 13) and because this is 1, stop.
(And better use Mod(3,13) instead of the incorrect Mod(3^13), hehe, yeah, I know that is a typo )

[axn]

znlog(2, Mod(3, 13))

[Dr Sardonicus]

If 3 is a quadratic residue (mod p) but 2 is a quadratic non-residue (mod p), then 3^n == 2 (mod p) is impossible. This situation is characterized by the linear congruences

p == 11 or 13 (mod 24).

Let q > 2 be a prime. Then as with quadratic residues, we can say, for p == 1 (mod q),

If 3 is a q-th power residue (mod p) but 2 is not a q-th power residue (mod p), then 3^n == 2 (mod p) is impossible.

Unfortunately, this situation is not characterized by linear congruences. One can test for the condition, for p == 1 (mod q),

3^(p-1)/q == 1 (mod p) but 3^(p-1)/q !== 1 (mod p).

Checking for q = 2, 3, 5, and 7 gives the following pairs [p, q] of disqualified primes p < 1000, with the smallest q disqualifying each.

[[11, 2], [13, 2], [37, 2], [41, 5], [59, 2], [61, 2], [67, 3], [73, 3], [83, 2], [103, 3], [107, 2], [109, 2], [131, 2], [151, 3], [157, 2], [179, 2], [181, 2], [193, 3], [227, 2], [229, 2], [251, 2], [271, 3], [277, 2], [347, 2], [349, 2], [367, 3], [373, 2], [397, 2], [419, 2], [421, 2], [431, 5], [443, 2], [467, 2], [491, 2], [523, 3], [541, 2], [547, 3], [563, 2], [577, 3], [587, 2], [613, 2], [619, 3], [659, 2], [661, 2], [683, 2], [709, 2], [733, 2], [757, 2], [761, 5], [787, 3], [827, 2], [829, 2], [853, 2], [877, 2], [883, 7], [947, 2], [967, 3], [971, 2], [991, 3], [997, 2]]

[Dr Sardonicus]

I done screwed up. That'll teach me to think before I post


Obviously, for p > 3, the condition that p divide 3^n - 2 for some n, is that the multiplicative order of 2 (mod p) divide the multiplicative order of 3 (mod p). And, this can happen even if 2 and 3 are both q-th power residues (mod p) for some prime divisor q of p - 1.

Examples are p = 193 (q = 2); 307 (q = 3) and 313 (q = 2).

[axn]

Originally Posted by Dr Sardonicus

I done screwed up. That'll teach me to think before I post


Obviously, for p > 3, the condition that p divide 3^n - 2 for some n, is that the multiplicative order of 2 (mod p) divide the multiplicative order of 3 (mod p). And, this can happen even if 2 and 3 are both q-th power residues (mod p) for some prime divisor q of p - 1.

Examples are p = 193 (q = 2); 307 (q = 3) and 313 (q = 2).

Is this correct for p>=5?

isimpossible(p)=Mod(2,p)^znorder(Mod(3,p))!=1

[devarajkandadai]

Originally Posted by LaurV

yes, you will only need to test for 3^2 (mod 13), and 3^3 (mod 13) and because this is 1, stop.
(And better use Mod(3,13) instead of the incorrect Mod(3^13), hehe, yeah, I know that is a typo )

Thank you and Dr. Sardonicus;will try

[Dr Sardonicus]

Originally Posted by axn

Is this correct for p>=5?

isimpossible(p)=Mod(2,p)^znorder(Mod(3,p))!=1

Looks good to me!

EDIT: It occurred to me to count how often each of several possible relations between the multipilcative orders occurred. I don't know what is suspected along these lines...

? c1=0;c2=0;c3=0;c4=0;forprime(p=5,10000000,n1=znorder(Mod(3,p));n2=znorder(Mod(2,p));if(n1!=n2&&n1%n2==0,c1++);if(n1!=n2&&n2%n1==0,c2++);if(n1%n2!=0&&n2%n1!=0,c3++);if(n1==n2,c4++));print([c1,c2,c3,c4])
[195328, 195135, 86169, 187945]