341

This article is about a particular natural number.|View all articles on particular natural numbers

Summary

Factorization

The factorization is as follows, with factors 11 and 31:

$341=11*31$

Properties and families

Property or family	Parameter values	First few members of the family	Proof of satisfaction/membership/containment
Poulet number (also called Sarrus number), i.e., Fermat pseudoprime to base 2	smallest Poulet number	341, 561, 645, 1105, 1387, 1729, 1905, 2047, [SHOW MORE] 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, 10261, 10585, 11305, 12801, 13741, 13747, 13981, 14491, 15709, 15841, 16705, 18705, 18721, 19951, 23001, 23377, 25761, 29341 View list on OEIS	$2^{10}=1024\equiv 1{\pmod {341}}$, so $2^{340}\equiv 1{\pmod {341}}$.

Arithmetic functions

Function	Value	Explanation
Euler totient function	300	The Euler totient function is $(11-1)(31-1)=(10)(30)=300$.
universal exponent	30	The universal exponent is $\operatorname {lcm} \{10,30\}=30$.
divisor count function	4	$(1+1)(1+1)$ where the first 1s in both factors are the multiplicities of the prime divisors.
divisor sum function	384	$(11^{2}-1)/(11-1)$ times $(31^{2}-1)/(31-1)$ equals $(12)(32)=384$.
Mobius function	1	The number is square-free and has an even number of prime divisors (2 prime divisors).

Structure of integers mod 341

Abstract structure

The discussion here about the multiplicative group of integers modulo n relies on some background facts from group theory.
FACTS ABOUT MULTIPLICATIVE GROUPS: Classification of natural numbers for which the multiplicative group is cyclic | Characterization of multiplicative group of integers modulo n
GENERAL FACTS ABOUT GROUPS: order of direct product is product of orders, exponent of direct product is lcm of exponents

By the Chinese remainder theorem, we have the ring decomposition:

$\mathbb {Z} /341\mathbb {Z} \cong \mathbb {Z} /11\mathbb {Z} \times \mathbb {Z} /31\mathbb {Z}$

For the multiplicative group, this gives:

$(\mathbb {Z} /341\mathbb {Z} )^{*}\cong (\mathbb {Z} /11\mathbb {Z} )^{*}\times (\mathbb {Z} /31\mathbb {Z} )^{*}$

Both groups on the right side are cyclic with orders 10 and 30 respectively, so the whole group is:

$(\mathbb {Z} /341\mathbb {Z} )^{*}\cong \mathbb {Z} /10\mathbb {Z} \times \mathbb {Z} /30\mathbb {Z}$

This group has order $10\times 30=300$ (the order of the multiplicative group is termed the Euler totient function and denoted $\varphi$, so this is saying that $\varphi (341)=300$).

The exponents of the factor groups are 10 and 30 respectively, hence the exponent of the whole group is the lcm of these, which is 30. The exponent of the multiplicative group is termed the universal exponent and denoted $\lambda$, so this is saying that $\lambda (341)=30$).

Primality testing

Summary

Primality test	Relies on ...	Total number of candidate bases	Number of bases wih gcd more than 1	Number of witnesses that are relatively prime	Number of liars that are relatively prime	Total number of witnesses	Probability of picking witness	Probability of picking liar	Conditional probability of picking witness for relatively prime	Conditional probability of picking liar for relatively prime
Fermat primality test	Fermat's little theorem	340	40	200	100	240	240/340 = 12/17	100/340 = 5/17	2/3	1/3
Solovay-Strassen primality test	Euler's criterion	340	40	?	?	?	?	?	?	?
Miller-Rabin primality test		340	40	?	?	?	?	?	?	?

Fermat test

341 is a Fermat pseudoprime to base $a$ if the order of $a$ mod 11 divides 340 and the order of $a$ mod 31 divides 340. The first condition always holds, because 11 - 1 = 10 divides 340. The second condition is equivalent to the order dividing 10, which holds for 1/3 of the bases relatively prime to 31. Overall, 341 is a Fermat pseudoprime for 1/3 of the 300 possible bases relatively prime to it (i.e., a total of 100 possible bases). This means that if we use the Fermat test for a base picked at random, there is a 2/3 chance that we will be able to use it to conclude that 341 is not prime.

2 is one of the bases for which 341 is a Fermat pseudoprime, because $2^{10}=1024\equiv 1{\pmod {341}}$. Thus, 341 is a Poulet number or Sarrus number.

Euler test

Fill this in later

Strong Fermat test

Fill this in later