Question

Euler discovered that the polynomial p(n) = n^2 - n + 41 yields prime numbers for many small positive integer values of n. What is the smallest positive integer n for which p(n) and p(n+1) share a common factor greater than 1?

Answer 1

@ganeshie8 you might like this question

Answer 2

I don't know if we can do anything with this... but I have:
\[\frac{n+1}{2} p(n)-\frac{n-1}{2}p(n+1)=41\]

Answer 3

Did a couple of polynomial division problems to get that...
You know like euclidean algorithm stuff.

Answer 4

n^2 -n + 41 = n(n-1) + 41

plugin n = 41 or 42 :P

Answer 5

i think this is @cwrw238 's favorite problem

Answer 6

wait sry i misread the question, it looks a bit more involved..

Answer 7

I think from that equation above n is odd
just thinking
I want the (n+1)/2 and (n-1)/2 to be integers

Answer 8

But also like I said before I don't know if that equation helps yet

Answer 9

But also like I said before I don't know if that equation helps yet

Answer 10

for what @ganeshie8 said
n=41 does give gcd 41
but I think for n=42 it gives gcd 1

I wonder if n=41 is the lowest positive integer n such that the gcd is >1

Answer 11

Ahh that actually works!

p(41) and p(42) are actually composite with a gcd of 41

Answer 12

p(n) = `n(n-1)` + 41

plugging in n=41 or 42 makes the first term have a factor of 41

Answer 13

ah
p(41)=41(40+1)
p(42)=41(42+1)

Answer 14

@danyboy9169 just mentioning you here because I think you opened up a new question. just wanted to make sure you see the discussion here.

Answer 15

Yes, I did bumped it again as this is Number Theory descrete math, been searching for last 4 hrs now.. but if I know that for two consecutive nos. gcd is always 1.

Answer 16

\[\frac{n+1}{2} p(n)-\frac{n-1}{2}p(n+1)=41 \\ \text{ this means we can either have } \gcd(p(n),p(n+1))=1 \\ \text{ or } \gcd(p(n),p(n+1))=41\]
those are the only two possibilities
------------
p(41) and p(42) are not consective though

41 and 42 are though

Answer 17

Oh you're using that linear combination thingy here

ax + by = c

for above equation to make sense, we must have gcd(a,b) | c

only 1 and 41 divide 41 so we're done.

Answer 18

ci (yes; I think ci is spanish word for yes (it might be si))

Answer 19

thanks a ton freckles and ganeshie8

Answer 20

as i see now thats actually pretty clever !