#mersenne primes demo please!!

116 messages · Page 1 of 1 (latest)

jolly nymph
#

!

neat agate
#

What do you need to be explained?

#

Mersenne primes are prime numbers with the form

#

$M = 2^n - 1$

calm hollyBOT
#

Jadεn

1087130036081020978.png
neat agate
#

For an integer n

#

It's proven that for a composite number n, 2^n - 1 isn't prime

#

And not for all prime n, 2^n - 1 is prime

#

There is a sequence of primes that give off Mersenne primes

#

There is a method to check if M_p is prime(M_p = 2^p - 1)

#

$\forall p > 2, M_p = 2^p - 1 \text{ is prime iff } M_p | S_{p-2}, \text{ where } S_0 = 4 \text{ and } S_k = (S_{k-1})^2 - 2 \text{ for } k > 0$

calm hollyBOT
#

Jadεn

1087130036081020978.png
neat agate
#

This is the most efficient method known so far

#

You can implement it into a python code

#

and it can do it pretty fast

kind cipher
#

https://en.m.wikipedia.org/wiki/Mersenne_prime

Mersenne prime

In mathematics, a Mersenne prime is a prime number that is one less than a power of two. That is, it is a prime number of the form Mn = 2n − 1 for some integer n. They are named after Marin Mersenne, a French Minim friar, who studied them in the early 17th century. If n is a composite number then so is 2n − 1. Therefore, an equivalent defini...

kind cipher
neat agate
#

The "Searching for mersenne primes" section

kind cipher
#

o0 ill give it a read

neat agate
#

Here is it

#

I can work on it more and then send it

#

A python script that can check if the number 2^p - 1(the user gives p) is a marsenne prime

#

The "is_prime" function has a lot of recursion, I need to fix that

#

@jolly nymph Do you want the python script? Bc if not, I don't have to work on it and send it

#

and if you @kind cipher are interested, I can send it to you 🙃

neat agate
#

I found out that S_k grows exponentially

#

S(11) is too big for my computer to ahndle

#

so writing this code isn't going to work for me

#

lol

jolly nymph
#

good exercise but it's in french

#

tkyo btw

#

@neat agate

neat agate
#

I can read french

#

I'm from Morocco 🤓

#

You are too

#

I think I know that school

#

IQrae

#

I forgot if that upwards arrow means the greatest common divisor or not

#

I had taken that lesson at the start of this year

kind cipher
#

Thanks i annoyed my dad whos learning French with this

neat agate
#

Or is it the logical and

neat agate
#

@jolly nymph what does that upwards arrow mean?

kind cipher
#

coprime i think

neat agate
#

No

#

I took this lesson the same year

#

this year

#

It's the GCD or smth

#

We had them in French

#

the PGCD and something else

jolly nymph
#

yup it is

neat agate
#

Isn't it the PPCM?

#

I'm confused

#

The PGCD has "v"

jolly nymph
#

huh

neat agate
#

Show me your notes

#

Like the part where you did this in class

#

I lost my note book

jolly nymph
#

i don't have a note book hh

#

Look pgcD upwards like D but PPCM downward like M

neat agate
#

Yeah

#

That's what I remember too

#

Just give a sec

#

But they didn't give a symbol of the PPCM

#

So I assume they're wrong

#

"v" this is the PPCM and "^" is the PGCD

jolly nymph
#

yes they're

neat agate
#

Okay, so let's look at the first exercise

#

We need to use the formula for the PGCD

#

Take all the common divisors of the two and multiply them with the smallest exponents of the two numbers

#

But here m and n are arbitrary

jolly nymph
#

d|d' and d'|d <=> d=d'

neat agate
#

Yes, I know that

#

How can we use it here?

jolly nymph
#

let M(n)^M(m)= d and M(m^n)=d'

neat agate
#

Okay

#

Then we check

#

Yeah

#

$M(n) \land M(m) = 2^n - 1 \land 2^m - 1$

calm hollyBOT
#

Jadεn

1087130036081020978.png
neat agate
#

How can we simplify this?

jolly nymph
#

congru in english what is it?

neat agate
#

Congruent

jolly nymph
#

d' = M(m^n) , let m^n = L so 2 ^L = 1 [d'] (m^n = L<=> n=kL and m=k'L ) 2 ^Lk = 1[d'] and 2^Lk' = 1 [d'] => d' | 2^n -1 and d'|2^m -1

#

so d'|M(n)^M(m)

neat agate
#

Yes

#

I get it

jolly nymph
#

hrira

neat agate
#

hhh

#

wlah

jolly nymph
#

d|d'

neat agate
#

This is going to take a long time

#

And where do you need mersenne primes?

#

I mean M(n) is the form of a mersenne prime

#

but is there a question

#

about it?

jolly nymph
#

no

neat agate
#

Oh

jolly nymph
neat agate
#

Yes

#

But mersenne primes aren't easy to work with

#

and they grow very fast

#

But you can go read the wikipedia article

#

it may help you

#

bye for now

jolly nymph
#

see u later

ancient canopy
#

$M = 2^n - 1$

calm hollyBOT
#

rockhoven

699627666319605861.png