This is a prime problem

Let N N be the sum of all positive primes p p such that p 100 p≤100 which can be expressed in the form p = m 2 + n 2 p =m^2 + n^2 , where m m and n n are distinct positive integers. What is the value of N mod 29 N\text { mod } 29 ?


The answer is 22.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Curtis Clement
Jan 3, 2015

Using Fermat's square prime Theorem: If p {p} = m 2 m^{2} + n 2 n^{2} , then p {p} 1 \equiv1 mod(4). Searching for primes is relatively simple, so we do 5+13+17+29+37+41+53+61+73+89+97 = 515 22 \equiv22 mod(29). (Note: 2 is an exception to the rule, but m=n is forbidden in the question)

that's perfect. here is nice pdf on the same topic: http://eulerarchive.maa.org/docs/translations/E228en.pdf.

Sathvik Acharya - 4 years, 3 months ago
Jesse Nieminen
Mar 15, 2017

We can easily find than p = 2 p=2 is not a solution. Now, Fermat's theorem on sums of two squares tells that an odd prime p p can be expressed as a sum of two squares if and only if p 1 ( m o d 4 ) p \equiv 1 \pmod{4} . The squares must be distinct because one of them must be even and one of them must be odd.

Hence, the answer is 5 + 13 + 17 + 29 + 37 + 41 + 53 + 61 + 73 + 89 + 97 515 22 ( m o d 29 ) 5+13+17+29+37+41+53+61+73+89+97 \equiv 515 \equiv \boxed{22} \pmod{29} .

Squares are:
m 2 m^2 :- 1, 9, 25, 49, 81 and
n 2 n^2 :- 4, 16, 36, 64.

Sum of 'p's is : 5+13+17+29+37+41+ 53+61+73+89+97 =515....515 (mod 29) =22.
22 \boxed { 22 }
I am adding this now on 11/6/2014.

We can find 5,13,17,......97 through a table. Column with m 2 m^2 when ' m 'as odd (1, 3, 5, 7, 9), and row with n 2 n^2 when 'n' as even (2, 4, 6, 8) since p< 101.
Put the sum of column and row at an intersection if it is a prime or X if it is not a prime or it is greater than 100. We will have X at nine places (25, 45, 65, 85, 85, 114, 117, 145). Remaining numbers as given above. Add them up and (mod 29) = 22.
There is a little long method but intresting.
While filling up the table, for every item in the first column and row,have the
(mod 29) of it in the paranthises. At the intersection also have a parenthises that contain the sum of column paranthises and row parenthises. Finaly add only the numbers in the parenthises algebrically. The sum (mod 29) will be = 22.
For example intersection of column with 25 and row 16 would look like
.............................25(-4)
16(16)............... 41(12)

You forgot the prime 2 = 1 + 1

Steven Perkins - 6 years, 7 months ago

Log in to reply

We may not be using the same digits twice. If we do, you are right, I forgot 2. Correct answer given should than change to 24.

Niranjan Khanderia - 6 years, 7 months ago

Log in to reply

@Shreya R I think you have to say that m m and n n are distinct positive integers or that p p is odd.

milind prabhu - 6 years, 7 months ago

Log in to reply

@Milind Prabhu I agree with you. That makes things clear.

Niranjan Khanderia - 6 years, 7 months ago

Log in to reply

@Niranjan Khanderia Yeah i corrected it :)

Shreya R - 6 years, 7 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...