mersenneforum.org > Math Pseudoprimes in special fields
 Register FAQ Search Today's Posts Mark Forums Read

 2017-12-01, 05:12 #1 devarajkandadai     May 2004 22·79 Posts Pseudoprimes in special fields 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.
 2017-12-01, 06:12 #2 CRGreathouse     Aug 2006 22×3×499 Posts 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.
 2017-12-02, 17:46 #3 Dr Sardonicus     Feb 2017 Nowhere 2·5·653 Posts 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 C8 x C24 x C42 The subgroup of elements of orders dividing 104 is then easily seen to be C8 x C8 x C2 which has order 128.
 2017-12-03, 16:41 #4 Dr Sardonicus     Feb 2017 Nowhere 2·5·653 Posts 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
2017-12-05, 03:26   #5

May 2004

22×79 Posts

Quote:
 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.

Last fiddled with by devarajkandadai on 2017-12-05 at 03:30 Reason: want to be more explicit

 2017-12-05, 03:52 #6 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 2·5·7·13 Posts 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.
2017-12-05, 14:00   #7
Dr Sardonicus

Feb 2017
Nowhere

2·5·653 Posts

On 2017-12-01, 05:12,
Quote:
 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:
Quote:
 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.

2017-12-06, 01:46   #8

May 2004

22×79 Posts

Quote:
 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).

 Similar Threads Thread Thread Starter Forum Replies Last Post TheoryQuest1 Factoring 10 2016-09-19 16:08 CRGreathouse Computer Science & Computational Number Theory 36 2013-11-21 07:47 Raman Miscellaneous Math 5 2013-06-12 13:54 efeuvete Math 7 2013-05-26 11:24 meng_luckywolf Math 6 2007-12-13 04:21

All times are UTC. The time now is 14:36.

Sun Oct 1 14:36:22 UTC 2023 up 18 days, 12:18, 0 users, load averages: 0.96, 0.77, 0.75