Plz solve this Question..
.......Step by step ...........
........Don't Samping.......
Answers
However, it is interesting to note that n2+n+41 is indeed prime for any integer in [0,39] .
We can check this by computing all those values, but I claim that it suffices to check P(0) , P(1) , P(2) and P(3) where P(n)=n2+n+41 .
What’s the “easiest” way to know if a number is a prime ? You check that it’s not divisible by any prime less than its square root.
Since we’re dealing with n∈[0,39] and P is increasing: P(n)<P(40)=1681
So, to check if P(n) is prime, it suffices to show that it’s not divisible by any prime number p<1681−−−−√=41
I will prove this using fake induction (It looks like induction but it’s not quite, since we’re not proving this for all integers)
Let k≤39 be an integer. I will assume P(m) is prime for 0≤m<k and I will prove that P(k) is also prime:
Let p be the smallest prime divisor of P(k) . If p=P(k) , we’re done!
Otherwise np=P(k) with n>1 .
I’m going to assume that 7<p<41 . Let’s consider these following cases:
p≤k :
Notice that P(k)≡P(k−p)mod p . In addition, 0≤k−p<k so by our “induction” hypothesis P(k−p) is prime, and p≤41<P(k−p) , so P(k−p)≠p , hence p doesn’t divide P(k) . Contradiction.
2. k<p :
This case takes slightly more work. First of all, notice that:
P(k)≡k(k+1)+41≡−k(−k−1)+41
≡(p−k)(p−k−1)+41≡P(p−k−1)mod p
Again, we’re gonna need cases:
a) If p−k−1<k , We have a contradiction. (since by induction hypothesis P(p−k−1) is prime larger than p , so it can’t be divisible by p )
b) k≤p−k−1⇔k≤p−12 :
This means np=P(k)≤P(p−12)=p2−14+41<p2 since p> 7 (*)
So 1<n=P(k)p<p2p=p .
In other words, n is a divisor of P(k) that is smaller of p , this contradicts the minimality of p !(Remember, p was chosen to be the smallest prime divisor of P(k) )
Now what if p≤7 ? Well, that also can’t happen since:
P(k) is always odd
checking P(0) and P(1) proves that P(k) is never divisible by 3
Checking P(0) , P(1) and P(2) proves that P(k) is never divisible by 5
Checking P(0) , P(1) , P(2) and P(3) proves that P(k) is never divisible by 7 .
This completes the proof.
Note: You might might be wondering, what’s so special about 41 ? Can’t I do this with any integer? Well, if k is an integer and Q(n)=n2+n+k , then we can prove the following:
Q(n) is prime ∀n∈ [0,k−2] ⟺ Q(n) is prime ∀n∈[0,⌊k3−−√⌋] .
(note that ⌊413−−√⌋=3, which is why we only needed to check up to P(3) )
The proof of the general case is pretty much identical to the one I provided above.
Such integers k are called Lucky numbers of Euler and there is exactly 7 of them, namely : 1 , 2 , 3 , 5 , 11 , 17 and 41 .
Answer: