341

From Number
Jump to: navigation, search
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:

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] View list on OEIS , so .

Arithmetic functions

Function Value Explanation
Euler totient function 300 The Euler totient function is .
universal exponent 30 The universal exponent is .
divisor count function 4 where the first 1s in both factors are the multiplicities of the prime divisors.
divisor sum function 384 times equals .
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:

For the multiplicative group, this gives:

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

This group has order (the order of the multiplicative group is termed the Euler totient function and denoted , so this is saying that ).

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 , so this is saying that ).

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 if the order of mod 11 divides 340 and the order of 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 . Thus, 341 is a Poulet number or Sarrus number.

Euler test

Fill this in later

Strong Fermat test

Fill this in later