Pseudoprimes in special fields

[devarajkandadai]

Consider the special field: Mod(x^2+7).
Then ((15+7*sqrt(-7))^104-1)/105 is equal to an integer in this field i.e. 105 is a Fermat pseudoprime in the field under consideration.

[CRGreathouse]

I assume you're talking about the field \(\mathbb{Q}(\sqrt{-7})\)? Or really, the ring of integers \(\mathcal{O}_{\mathbb{Q}(\sqrt{-7})} = \left\{m + n\frac{1+\sqrt{-7}}{2}\ |\ m,n \in \mathbb{Z}\right\}\).

Yes, 105 is a pseudoprime to base 15+7*sqrt(-7). There are 255 other bases in the ring \(\mathcal{O}_{\mathbb{Q}(\sqrt{-7})}\) to which 105 is a pseudoprime, for example 20+7*sqrt(-7) and 65/2+21*sqrt(-7)/2.

[Dr Sardonicus]

I assume the ring in question is the ring R of integers in Q(sqrt(-7)). As long as the modulus n is an odd integer greater than 1, 2 is invertible (mod n), and you can express residues in R/nR in the form Mod(Mod(a,n) + Mod(b,n)*x,x^2 + 7).

In the case n = 105 = 3*5*7, the invertible elements of (R/105R)* may be expressed as the direct product

(R/3R)* x (R/5R)* x (R/7R)* which may easily be seen to be

C₈ x C₂₄ x C₄₂

The subgroup of elements of orders dividing 104 is then easily seen to be

C₈ x C₈ x C₂

which has order 128.

[Dr Sardonicus]

Again assuming we're working in the ring of integers R of Q(sqrt(-7)), I submit for your amusement

n = 5632705 = 5*13*193*449

for which x^(n-1) == 1 (mod n) for any x in R whose norm is relatively prime to n.

There are smaller such composite n, but I chose this one because of the factors 5 and 13
:-D

[devarajkandadai]

Originally Posted by CRGreathouse

I assume you're talking about the field \(\mathbb{Q}(\sqrt{-7})\)? Or really, the ring of integers \(\mathcal{O}_{\mathbb{Q}(\sqrt{-7})} = \left\{m + n\frac{1+\sqrt{-7}}{2}\ |\ m,n \in \mathbb{Z}\right\}\).

Yes, 105 is a pseudoprime to base 15+7*sqrt(-7). There are 255 other bases in the ring \(\mathcal{O}_{\mathbb{Q}(\sqrt{-7})}\) to which 105 is a pseudoprime, for example 20+7*sqrt(-7) and 65/2+21*sqrt(-7)/2.

I may be wrong but there seem to an infinite number of bases of form (15+ 7sqrt(-y)) where y is prime, excepting 3 and 5, for pseudoprimality of 105.

[danaj]

Made me think of https://arxiv.org/pdf/1307.7920.pdf and https://arxiv.org/pdf/1706.01265.pdf.

They may or may not actually have any connection to what you're discussing.

[Dr Sardonicus]

On 2017-12-01, 05:12,

Originally Posted by devarajkandadai

Consider the special field: Mod(x^2+7).
Then ((15+7*sqrt(-7))^104-1)/105 is equal to an integer in this field i.e. 105 is a Fermat pseudoprime in the field under consideration.

On 2017-12-05, 03:26, in the same thread, the poster changed the subject:

Originally Posted by devarajkandadai

I may be wrong but there seem to an infinite number of bases of form (15+ 7sqrt(-y)) where y is prime, excepting 3 and 5, for pseudoprimality of 105.

I don't care whether this is utter incompetence or deliberate trollery. I'm tired of it.

[devarajkandadai]

Originally Posted by devarajkandadai

I may be wrong but there seem to an infinite number of bases of form (15+ 7sqrt(-y)) where y is prime, excepting 3 and 5, for pseudoprimality of 105.

Charles, you have shown me how to identify rational integer bases for pseudoprimality of 105. Each of these can be split to form algebraic integer bases for the same-example: Have already shown that 22 can be split as 15+7*I, 15 + 7*I*sqrt(7) and many with shape 15 +7*sqrt(-y) where y is prime excepting 3 and 5.Next 8 can be split as 15 -7*I or 15-7*sqrt(-y) where y is prime. Have tested a few. Similarly 29 can be split as 15 + 14*sqrt(-y).