Question

Find one prime divisor of \(2^{5903}-1\)

Answer 1

if it helps use wolfram/programming/anything

Answer 2

ah, nope

Answer 3

I'm gonna go with 5903 itself. Since 5903 is prime and that makes thins one of thos eqs from number theory

Answer 4

dividing by 5903 leaves a remainder 1

Answer 5

I think it goes like \[2^p-1\equiv 0modp\]

Answer 6

hmmm

Answer 7

\[2^{p-1}-1\equiv 0 \pmod p\]

is true by fermat

Answer 8

p-1... darn

Answer 9

but i think you're on right track

Answer 10

idk maybe not.. my method is bit different...

Answer 11

idk, I was guessing cause it reminded me of that haha

Answer 12

hmm well, i'm gonna say that it is whatever \[2^{5903}-1\] is since 5903 is prime

Answer 13

so that number must be prime too

Answer 14

it is composite

Answer 15

i had to find a divisor in proving that it is composite

Answer 16

https://primes.utm.edu/notes/proofs/Theorem2.html
I was thinking this in reverse

Answer 17

well, I thought it was implied by the corollary

Answer 18

Ahh that works in one direction i think..
\(a^n-1\) is prime \(\implies\) \(n\) is prime and \(a=2\)

Answer 19

but then why not the other way? I mean this number ends in 7

Answer 20

yes units place is 7

Answer 21

it is congruent to 3 mod 4 I expect

Answer 22

but unless we rewrite that exponent somehow...

Answer 23

http://www.wolframalpha.com/input/?i=prime+factorization+2%5E11-1

Answer 24

ok

Answer 25

so if we were to say \[(2^2)^{5903/2}\]

Answer 26

interesting, yes it is 3 mod 4

Answer 27

is that one of those mersene numnbers

Answer 28

yes

Answer 29

it is a mersenne number but not a mersenne prime

Answer 30

saw a Numberphile video on those a while back, pretty interesting

Answer 31

so, it's not a prime, but it is congruent to 3 mod 4.... hmmmmm

Answer 32

it is composite for sure you an take my word for it till we find a divisor :)

Answer 33

ok just something I noticed, doesn't the number of prime factors for these numbers show the layout of twin primes???? http://mathworld.wolfram.com/MersenneNumber.html

Answer 34

it's super cool

Answer 35

....if not, I know I've seen that sequence before....

Answer 36

maybe it's the number of numbers between primes, but I know I have seen that sequence before... I used to write out a bunch of stuff like that

Answer 37

yay! a new project again!

Answer 38

i checked those oeis lists but couldnt find any of the divisors

here is one prime divisor of 2^5903 - 1 :
`15489473`

i have one more prime divisor thats much smaller than this

i really don't know how many more prime divisors are there as the number is pretty large
its getting pretty late over here.. il leave this question open and checkout in the morning. good luck everyone :)

Answer 39

There should be quite a few http://oeis.org/A046051 It is the 777th Mersenne number, but IDK if the prime factorizations have been done to that high

Answer 40

how do i expand the list ?

Answer 41

that I am not sure of yet

Answer 42

i mean that link is showing only the first few numbers

Answer 43

how did you figure out it is 777th mersenne number ?

Answer 44

5903 is the 777th prime, the numbers are generated by n where n maps p_1-->2 p_2-->3 so on and so on, right?

Answer 45

Omg yess got you :)

Answer 46

so if someone else has charted that, we could know how many factors there are easily, I would hope

Answer 47

so 777 is composite does imply that your number is composite quite quickly, I wonder if we said the number of factors of yours are \(Number~ of ~factors(M_3*M_7*M_37)\) if that would hold... That would give you 2 prime factors.

Answer 48

so if you have one, there is only one more?

Answer 49

nope... That unfortunately was disproven I think

Answer 50

but hey, I broke a website for ya, so be happy :)

Answer 51

9551342188655138465520630850748050237740825070468892272952870924644971060885980014797101592975604225394232178584042095438080874653033000331395103467735281328601695054847936491311527786671682592162023203313739961799537721188890561032015232740739319738333112751236122135697776461411064734226086042781330708005573085444012640234119134025335802746712411549041279893254970691479356955432922200407909731340402070631008165402702077757381508332714274047231528316463577958424135101308723835511153839289407331387837071445007284264743628515026257087054681121593156860426422949386744082801723391376251960500104779889096896085796997694877959326790879529168673362194818833716690707451436228868264143311645972611755728082963833538685570211392747634090165642002248970512159936093872616529809897187324891431584983442345523130705081126977817771847545510095508799677682071192057413296958123243781136260300990024753753003485045558304750628504680559293456024198635220012721581300440268692644730888654278822309815992095786163321036302624700675030450740050850140814899538810965000023356460637220447650815182582204557020578760952164279444934780918311159828233237536134274307033525441656137713203494335485237821182337824749946436459089651152619038477420024751551968999810256344722627877341947449539212500064909603404791421998814974051217774484619860053572148942068366595513913435156942402630948983804055905651162213754331132351212284929810561393370511275820187878030146314727136735033789567398009005283583734875313005061987943067150159176688822310958217907933010033542184922276062838408401300536480082515947239701583322577589591154094907178711808300932326795024101385254249838170624555401802817597058566015839803846142809468260749641012050369357086530748854455111175076440017518292017809047571302187007


That is our number

Answer 52

3 is the answer @ganeshie8

(a^p -1)/p is fully divisible by p
where a and p are prime numbers... fermat's remainder theorem.

Answer 53

a^p-1/p has a remainder of 1 by fermat's little thm, no?

Answer 54

ermm phi function failed :P
i'll try in morning

Answer 55

:3
i wish 5903 is not prime xD

Answer 56

Ohhh, @Kainui posted a really cool prime factorization link in one of his threads. I'll see if I can find it.

Answer 57

http://faculty.kutztown.edu/rieksts/OLD/341-F03/projects/ca-crypt/primes.html

Answer 58

Might help? Maybe.

Answer 59

first solution
11087

Answer 60

@Marki \[
3231\equiv 2^{5903}-1\pmod{11087}
\]

Answer 61

typo
i meant 11807

Answer 62

Hmmm, that looks like what I'm getting:
http://jsfiddle.net/wio_dude/c0cj428m/

Answer 63

I had tried earlier but wasn't finding any results because I had my exponent incorrect.

Answer 64

Wow! looks you guys nailed it ! wio that program runs super fast xD

Answer 65

@Marki im sure you must be having some cool number theory trick for finding divosors - please post your method when free (:

Answer 66

My method broke but let me type it out since I think it's interesting.

Answer 67

yes kai xD

Answer 68

\[\Large \sum_{k=0}^{5904} \frac{5904!}{k! \ (5904 - k)!}=2^{5904}\] Start here and take out the first and last terms of the series \[\Large \frac{1}{2} \sum_{k=1}^{5903} \frac{5904!}{k! \ (5904 - k)!}=2^{5903}-1\] But after typing this I just realized, the summation is symmetric, so we can just write it as: \[\Large \frac{5904! }{2(2952!)^2} + \sum_{k=1}^{2951} \frac{5904!}{k! \ (5904 - k)!}=2^{5903}-1\] So it looks like we can probably factor out something here, but I don't know what quite yet.

Answer 69

nice :) basically your strategy translates the problem to one of finding a common factor among first 5904 binomial coefficients very interesting idea XD il need to think about it more

Answer 70

I think "strategy" is too nice, I'm really just randomly trying stuff. I did come across this nice formula though: \[\Large \sum_{k=1}^a \left(\begin{matrix}a \\ k\end{matrix}\right) = \sum_{k=1}^a \left(\begin{matrix}a \\ k\end{matrix}\right) \frac{a+1}{2(a-k)}=2^a-1\]

Answer 71

It almost seems wrong when you look at it, but it is actually right. Haha

Answer 72

left and right sides are familiar to me
middle part looks new.. leme think a bit..

Answer 73

Hey kai, how did you get \[\Large \sum_{k=1}^a \left(\begin{matrix}a \\ k\end{matrix}\right) = \color{red}{\sum_{k=1}^a \left(\begin{matrix}a \\ k\end{matrix}\right) \frac{a+1}{2(a-k)}=2^a-1}\] everything in red

Answer 74

I think @ganeshie8 is trying to figure it out first. =P

Answer 75

Oh I see, ok

Answer 76

Or maybe I did write it wrong #_# let me check it... XD Sorry haha

Answer 77

right most reddy thing is a result of number of different ways of choosing a subset from a given set

middle part doesnt belong there

Answer 78

\[\sum \limits_{k=0}^n \binom{n}{k} = 2^n\]

Answer 79

this is an identity, im still trying to figure out middle part..

Answer 80

Corrected, whoops\[\Large \sum_{k=1}^a \left(\begin{matrix}a \\ k\end{matrix}\right) = \sum_{k=1}^a \left(\begin{matrix}a \\ k\end{matrix}\right) \frac{a+1}{2(a+1-k)}=2^a-1\]

Answer 81

Start with binomial theorem\[\Large \sum_{k=0}^{a+1} \frac{(a+1)!}{k! \ (a+1-k)!}=2^{a+1}\] Pull out the first and last terms (they're both 1) and inside pull out some numbers from the factorials \[\Large 2+\sum_{k=1}^{a} \frac{a!}{k! \ (a-k)!} \frac{a+1}{a+1-k}=2^{a+1}\] Move the 2 to the other side and factor out a 2 \[\Large \frac{1}{2} \sum_{k=1}^{a} \frac{a!}{k! \ (a-k)!} \frac{a+1}{a+1-k}=2^a-1\] There we go. =P

Answer 82

I wonder if we can rearrange that second term in there to be like the geometric series and sort of do some kind of cauchy product with it.

Answer 83

Looks nice :)
\[\binom{n}{k} = \binom{n}{k-1}\frac{n-k+1}{k}\]

Answer 84

that looks like a special case of newton's identity
\[\binom{n}{k} \binom{k}{r} = \binom{n}{r} \binom{n-r}{k-r}\]

lets see if we can use all these and pull some factor out xD

Answer 85

If we can do it generally, we would have a better idea of which mersenne numbers are primes maybe. Or maybe that will actually prevent us from doing it generally in the first place haha.

Answer 86

\[\frac{a+1}{a+1-k} = \frac{1}{1 - \frac{k}{a+1}}\]

like this kai ?

Answer 87

Yeah that's what I meant earlier. However that's inside a sum rather than outside it, so it's sort of not going to work I think.

Answer 88

Playing around I got this: \[\Large \frac{1}{2} \sum_{n=0}^\infty \sum_{k=1}^a \left(\begin{matrix}a \\ k\end{matrix}\right) \left( \frac{k}{a+1} \right)^n=2^a-1\]

Answer 89

More general alternative forms I'm playing with are:

a odd: \[\Large \sum_{k=1}^{(a-1)/2} \left(\begin{matrix}a \\ k\end{matrix}\right) \frac{a+1}{a+1-k}=2^a-1\]

a even: \[\Large \frac{a!}{2 (a/2)!^2} + \sum_{k=1}^{a/2} \left(\begin{matrix}a \\ k\end{matrix}\right) \frac{a+1}{a+1-k}=2^a-1\]

Answer 90

I am getting tired so maybe I messed one of those up, but I know this is true: \[\Large \frac{5904! }{2(2952!)^2} + \sum_{k=1}^{2951} \frac{5904!}{k! \ (5904 - k)!}=2^{5903}-1\] And upon looking at it, we can easily factor out 5904 and leave 5903! behind since that will always leave integers, so we're safe there.

Now we just need to see what factors of 5904 we can factor out of the other term. Well obviously since 2^asdofuao-1 is odd we just divide 5904 by 2 until we get an odd number which is 369. We factor this tiny number into 3*3*41. Since I know from mods that the last digit of the number is 7, 41 is not a factor, so I pray that it's 3 and post this and go to sleep.

Answer 91

>.< i was gonna post something like this