 mersenneforum.org > Math Pseudoprimes in special fields
 User Name Remember Me? Password
 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 5,987 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 135348 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 22×5×13×23 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 32·101 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

175C16 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

1001111002 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).  Thread Tools Show Printable Version Email this Page 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 21:27.

Wed Sep 28 21:27:39 UTC 2022 up 41 days, 18:56, 0 users, load averages: 1.02, 1.15, 1.06

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔