Competition - post a photo you've taken of nature >>

Official TSR Mathematical Society

Scroll to see replies

J.F.N

RichE

Yes of course I can see solutions like {2,2,7} and there may be infinitely many such triples (not sure how you'd show this). But I don't see how there could be three distinct primes. My reasoning went as follows, and just uses simple modular arithmetic. Can you give me a counter-example to it because I don't see its flaw?

Let p<q<r be three primes such that

p+q = a^2
p+r = b^2
q+r = c^2

Suppose (for a contradiction) that p,q,r are all odd. Then a^2,b^2,c^2 are all even - so a,b,c are all even. But then a^2,b^2,c^2 are all 0 mod 4.

If p = 1 mod 4 then q and r are 3 mod 4 and so q+r is 2 mod 4 - contradiction.
If p = 3 mod 4 then q and r are 1 mod 4 and so q+r is 2 mod 4 - contradiction.

So they cannot each be odd and hence p = 2.

Now we're looking to solve

2+q = a^2
2+r = b^2
q+ r = c^2

As the primes are distinct then q and r are odd and hence so are a^2 and b^2, whilst c^2 is even. Therefore a^2 and b^2 are 1 mod 4 and c^2 is 0 mod 4. (Square numbers are either 0 or 1 mod 4.)

So q and r are both 3 mod 4. Hence q+r is 2 mod 4 which contradicts the earlier proof that it was 0 mod 4.

QED - no such distinct triple of primes exists.

Can you spot the error? :confused:

Looks correct. My excuse, if it is one, is that the source of the question seemed to imply that a set of distinct primes does exist. (See http://www.people.fas.harvard.edu/~gcarroll/math/easier.pdf)

Reply 181

RichE

J.F.N

Looks correct. My excuse, if it is one, is that the source of the question seemed to imply that a set of distinct primes does exist. (See http://www.people.fas.harvard.edu/~gcarroll/math/easier.pdf)

Nevermind

, and that's something of a relief as I couldn't see an error - so you don't know of a counter-example? :rolleyes:

I guess it's the empty set then.

How many primes there are of the form m^2 - 2 I imagine is actually a very difficult problem. The Prime Number Theorem suggests it should be finite as the integral of 1/(x^2 logx) is finite towards infinity. But that's no proof - I imagine there's some difficult theorem akin to Dirichlet's for primes in a quadratic progression.

Reply 182

J.F.N

RichE

Nevermind

, and that's something of a relief as I couldn't see an error - so you don't know of a counter-example? :rolleyes:

I guess it's the empty set then.

I'm still quite naive as a mathematician.

RichE

How many primes there are of the form m^2 - 2 I imagine is actually a very difficult problem. The Prime Number Theorem suggests it should be finite as the integral of 1/(x^2 logx) is finite towards infinity. But that's no proof - I imagine there's some difficult theorem akin to Dirichlet's for primes in a quadratic progression.

I ran a code to see how often x^2-2 gives a prime. Let f(n) denote the number of times x^2-2 is prime as x goes from 1 to n. This is what I got:
f(10)=5
f(100)=26
f(1000)=157
f(10000)=1153
f(100000)=8888
f(1000000)=72928
f(10000000)=615643
...
My computer took precisely 11 minutes to compute that last one, so I think i'll stop here. Anyway, it doesn't look like its finite. Quick, devise an asymptotic formula! :wink:

Reply 183

RichE

J.F.N

Well of course that doesn't prove anything as n becomes large, though it is suggestive of infinite cases but I wasn't applying the PNT correctly anyway. :frown:

If the chance of n being prime is of the order of 1/logn then we would need to sum 1/log(n^2-2) to get a guesstimate from PNT and that series would diverge

Reply 184

J.F.N

RichE

Well of course that doesn't prove anything as n becomes large, though it is suggestive of infinite cases but I wasn't applying the PNT correctly anyway. :frown:

If the chance of n being prime is of the order of 1/logn then we would need to sum 1/log(n^2-2) to get a guesstimate from PNT and that series would diverge

A necessary and sufficient condition for a polynomial f(x) in Z[x] to have infinitely many prime values is for it to be irreducible over Z; this would include the condition that the GCD of the coefficients is 1. Certainly if f is reducible then each factor could take the value 1 only finitely many times (hence f can be prime only at a finite number of integers). In the case where deg(f)=1, Dirichlet's theorem confirms that ax+b will take infinitely many prime values if (a,b)=1. I tested this for a variety of cyclotomic polynomials: n^2+n+1, n^2+1, and n^3-n+1 for n up to 10^9. All returned values very close to the input (for example, n^3-n+1 for n up to 10^9 gave 999999986). Sadly, this sheds little light on the general case of irreducible polynomials.

Reply 185

RichE

J.F.N

Did you mean to write sufficient here? Whilst I can't think of counter-example off the top of my head, I hadn't realised this result was known and it seems to be at odds with what I thought were open results regarding primes amongst some quadratic progressions

Reply 186

J.F.N

RichE

Of course, it's not a proven result. I realize that I made it seem as so, but its a reasonable conjecture with sufficient evidence to back it (as Brian Birch has said, "the object of numerical computation is theoretical advance"). I am sort of 'convinced' that x^2 -2 also takes infinitely many prime values--unless you're confident that it doesn't. As you point out, there are still many open results regarding primes generated by quadratics, the most famous of which is probably x^2 + 1.

P.S. I don't know if anyone has shown that there is a counterexample, i.e. an irreducible polynomial in Z with only finitely many prime values. It may be true for the cyclotomic polynomials I tested, but this does nothing to give a hint of the general case. Surely this is a much more difficult conjecture to prove.

Reply 187

dvs

I thought I'd kick this thread back up with a new problem:

Let f(n) denote the digital sum of n, where n

\in

N. For example, f(345)=3+4+5=12. Solve:
n + f(n) + f(f(n)) = 1997

Reply 188

Gaz031

Clearly if N>0 then f(N)>0. Thus we know n

\leq

1997 and hence that the number n is composed of four digits or less.

Let n=abcd (not the product - sorry for the awful notation!)
f(n)=00ef (ef=a+b+c+d) (note that ef=f(n)

\leq

1+9+8+9=27 and e

\leq

2)
f(f(n))=00gh (gh=e+f) (note that gh=f(f(n))

\leq

1+9=10 so either (g=1, h=0) or g=0)

Thus we have:
(a)(b)(c+e+g)(d+f+h)=1997

Hence a=1, b=9 and:
c+e+g=9
d+f+h=7
ef=10+c+d

\leq

27
gh=e+f

\leq

10

Assume first that g=1 and h=0:
c+e=8
d+f=7
ef=10+c+d

\leq

27
10=e+f

Then e=1 or e=2
If e=1, f=9, d+f=7 cannot be satisfied and so e

\neq

1
If e=2, f=8, d+f=7 cannot be satisfied and so e

\neq

2

Thus we are forced to assume g=0
c+e=9
d+f+h=7
ef=10+c+d

\leq

27
h=e+f

\leq

9
Now again e=1 or e=2.

If e=1 we have c=8 and n=198k
If k=0, n+f(n)+f(f(n))=1980+18+9>1997
If k=1, n+f(n)+f(f(n))=1981+19+10>1997
If k=2, n+f(n)+f(f(n))=1982+20+2>1997
..
..
Checking all cases shows e

\neq

1

If e=2 we have c=7 and n=197k
If k=0, n+f(n)+f(f(n)) = 1970+17+8=1995
If k=1, n+f(n)+f(f(n)) = 1971+18+9=1998
If k=2, n+f(n)+f(f(n)) = 1972+19+10=2001
If k=3, n+f(n)+f(f(n)) = 1973+20+2=1995
..
..
Checking all cases shows e

\neq 2

Thus we have no solutions.

Edit: There's a slight problem here in that we are assuming that c+e+g

\leq

9(i.e.

c\leq 6

and d+f+h

\leq

9. There should be a way to fix this somehow...

Reply 189

dvs

Heh.. Excellent. :biggrin:

Your answer is correct: there are no solutions. I'm not entirely sure your method is, but I haven't read it through yet.

There's a quicker solution that involves looking at remainders when you divide by 3 (i.e. considering mod 3). I won't post it yet though.

p.s. :rolleyes:

Reply 190

Jonny W

Let F(n) = n + f(n) + f(f(n)).

Claim 1
There is a function g: N -> Z such that f(n + 1) - f(n) = 1 - 9g(n).

Proof
g(n) = number of zeros at the end of (n + 1).

Claim 2
There is a function h: N -> Z such that f(f(n + 1)) - f(f(n)) = 1 - 9h(n).

Proof
By Claim 1, f(n + 1)

\neq

f(n). If f(n + 1) > f(n) then

f(f(n + 1)) - f(f(n))
=

\sum_{m = f(n)}^{f(n + 1) - 1}

[f(m + 1) - f(m)]
=

\sum_{m = f(n)}^{f(n + 1) - 1}

[1 - 9g(m)]
= (f(n + 1) - f(n)) - 9

\sum_{m = f(n)}^{f(n + 1) - 1}

g(m)
= 1 - 9g(n) - 9

\sum_{m = f(n)}^{f(n + 1) - 1}

g(m)

Similarly if f(n + 1) < f(n).

Claim 3
For all n >= 1, F(n + 1) - F(n) is a multiple of 3.

Proof
F(n + 1) - F(n)
= 1 + [f(n + 1) - f(n)] + [f(f(n + 1)) - f(f(n))]
= 3 - 9g(n) - 9h(n)

Claim 4
For all n >= 1, F(n) is a multiple of 3.

Proof
Since F(1) = 3, the result follows from Claim 3.

--

Since 1997 is not a multiple of 3, the equation F(n) = 1997 has no solutions.

Reply 191

dvs

Also correct. Your solution was essentially the one I was looking for.

Suppose n = a[1]*10^k + a[2]*10^(k-1) + ... + a[k+1], then:
f(n) = a[1] + a[2] + ... + a[k+1]

Now:
n = a[1] + a[2] + ... + a[k+1] (mod 3)
=> f(n) = n (mod 3)
=> f(f(n)) = f(n) = n (mod 3)

Hence:
n + f(n) + f(f(n)) = 0 (mod 3)

So we have:
0 = 2 (mod 3)
i.e. no solutions.

Reply 192

Lecter

Can i join society of maths???

Reply 193

SketchyCanvas~

can i join please? Wishing to do maths as a full a level :biggrin:

Reply 194

J.F.N

Here's another (moderately difficult) question: find all positive integers m,n such that m|n^2 + 1 and n|m^2 + 1. The solution set is fairly interesting.

Reply 195

mizfissy815

Hey....can I join too?

Reply 196

einsci

I am 14 and enjoy maths very much. I am young but I think I am abled! :biggrin:

Please let me join!!!!!

Reply 197

Gaz031

J.F.N

Here's another (moderately difficult) question: find all positive integers m,n such that m|n^2 + 1 and n|m^2 + 1. The solution set is fairly interesting.

I'll post my thoughts so far - they aren't much I'm afraid.

We know an even number can't divide an odd number and that the square of an even number is even while the square of an odd number is odd. Hence m and n cannot possibly both be even.

Consider m|n²+1
Set n=am+b, where a and b are non negative integers and b<m (note am+b could denote any number with appropriate choice of a and b).
Then we need m|a²m²+2abm+b² and so need m|b²
We can repeat this process with n|m²+1 to obtain the result n|d² where d is a non negative integer and d<n.

Thus we have:
m|b², where b is some non negative integer less than m.
n|d², where d is some non negative integer less than n.

Hence m and n both belong to the same set.

To be a member of the solution set, a number must divide the square of some (integer below itself).

We can see from 1|0² that 1 is a solution. Also note any of the square numbers will be members as x²|x² (and x<x² for all integers greater than 1).

But then again, seeing 9 is a member we can't possibly have m=n=9 and so need some way to pair our m,n.

Not sure from there :rolleyes:

Reply 198

xx007

Hi, i enjoy maths n ill be taking up maths and further maths for as levels. can i join this society?

Reply 199

username9816

Proof (Attempt): Any positive integer ending in the digit 3 is not a perfect square

Lets assume that a positive integer ending in 3 is a perfect square.

We could then write x^2 = n*digits3, where n is a +ve integer and x^2 equals any +ve integer ending in the digit 3. For this +ve integer; if x is a +ve integer then we can say that it is a perfect square.

For any +ve integer ending in the digit 3, there are 3 possibilities to consider:

1.) It can be prime. e.g.) 13, 23 etc.

2.) It is composed of the product of distinct primes. e.g.) 33 = 11 * 3, where 11 and 3 are distinct primes.

3.) It is composed of the product of an odd number of a specific prime. e.g.) 243 = 3^5.

For possibility 1:

x^2 = p, where p is a prime number

-> x = Sqrt( p )

The square root of any prime gives an irrational. This is because if the converse was true, then this means that p is a perfect square. But p cannot contain any factors other than 1 and itself (by definition); p^2 =/= p <-> p^2 =/= p and 1^2 =/= p <-> Sqrt( p ) =/= 1. As neither case implies that p is a perfect square, then my original proposition is true.

Hence x must be irrational

Therefore prime p ending in digit 3, is not a perfect square.

For possibility 2:

x^2 = p.a, where p and a are distinct primes

-> x = Sqrt( p ). Sqrt( a )

Sqrt( p ) and Sqrt( a ) are each irrational for the reason explained above.

The product of 2 distinct irrationals, whereby each irrational is the square root of a unique prime, will yield an irrational.

Hence x must be irrational.

Therefore p.a ending in digit 3, is not a perfect square.

For possibility 3:

x^2 = p^n, where p is prime and n is an odd +ve integer.

-> x^2 = p.p.p...n times

-> x = Sqrt( p ). Sqrt( p )...n times

The product of Sqrt( p ) an odd number of times will leave the product of a rational and Sqrt( p ). Remember Sqrt ( p ) is irrational, explained earlier on. The product of (n - 1) Sqrt ( p )'s will yield a rational since an even number of identical irrationals are being multiplied. i.e.) [Sqrt( p )]^(n - 1) = {[Sqrt( p )]^2}^(n - 3) = p^(n - 3) -> Rational. The resulting product of a rational and an irrational therefore yields an irrational.

Hence x is irrational.

Therefore p^n ending in digit 3, is not a perfect square.

Conclusion: As neither possibility will yield a +ve integer ending in the digit 3 that is a perfect square, therefore any +ve integer ending in the digit 3 cannot be a perfect square.

* Special thanks go to Gaz for giving me this Maths question. :biggrin: