mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2017-12-01, 05:12   #1
devarajkandadai
 
devarajkandadai's Avatar
 
May 2004

22×79 Posts
Default 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.
devarajkandadai is offline   Reply With Quote
Old 2017-12-01, 06:12   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2017-12-02, 17:46   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

135348 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2017-12-03, 16:41   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×5×13×23 Posts
Default

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
Dr Sardonicus is offline   Reply With Quote
Old 2017-12-05, 03:26   #5
devarajkandadai
 
devarajkandadai's Avatar
 
May 2004

22×79 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
devarajkandadai is offline   Reply With Quote
Old 2017-12-05, 03:52   #6
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

32·101 Posts
Default

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.
danaj is offline   Reply With Quote
Old 2017-12-05, 14:00   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

175C16 Posts
Default

On 2017-12-01, 05:12,
Quote:
Originally Posted by devarajkandadai View Post
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 View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2017-12-06, 01:46   #8
devarajkandadai
 
devarajkandadai's Avatar
 
May 2004

1001111002 Posts
Default

Quote:
Originally Posted by devarajkandadai View Post
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).
devarajkandadai is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
On generating Strong PseudoPrimes DataBase? TheoryQuest1 Factoring 10 2016-09-19 16:08
Pseudoprimes CRGreathouse Computer Science & Computational Number Theory 36 2013-11-21 07:47
Questions about Number Fields Raman Miscellaneous Math 5 2013-06-12 13:54
Odd Fibonacci pseudoprimes efeuvete Math 7 2013-05-26 11:24
On the basis of finite fields 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

Powered by vBulletin® Version 3.8.11
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.

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