Test question

[lukerichards]

As many know, I'm a high school teacher.

I have a very high ability class who are studying for the UK's extended age-16 qualification called Additional Maths.

When the course required teaching iterative formulae (at a similar time to the main GCSE qualification also required them to revise basic division techniques) I decided to teach them them the Lucas Lehmer Primality Proof for Mersenne primes.

They know I'm obsessed with primes anyway, so this didn't come as much of a surprise to them.

They have recently been given an internal exam, NOT written by me which includes the following question:

Mersenne primes are prime numbers that can be written in the form where n is a whole number.

For example, 3 can be written as

Prove that is not a Mersenne prime.

I'm not sure whether to be pleased or disappointed that, thus far (I haven't finished marking them) they have all used trial division rather than a LL test. Trial division is, of course, the much more efficient way of proving the compositeness of this number!

[xilman]

Originally Posted by lukerichards

As many know, I'm a high school teacher.

I have a very high ability class who are studying for the UK's extended age-16 qualification called Additional Maths.

When the course required teaching iterative formulae (at a similar time to the main GCSE qualification also required them to revise basic division techniques) I decided to teach them them the Lucas Lehmer Primality Proof for Mersenne primes.

They know I'm obsessed with primes anyway, so this didn't come as much of a surprise to them.

They have recently been given an internal exam, NOT written by me which includes the following question:



I'm not sure whether to be pleased or disappointed that, thus far (I haven't finished marking them) they have all used trial division rather than a LL test. Trial division is, of course, the much more efficient way of proving the compositeness of this number!

I did Additional Maths at A Level way back when.

Even faster than trial division is to prove that 2^pq-1 is divisible by both 2^p-1 and 2^q-1, thereby showing that a composite exponent can never yield a Mersenne prime.

To those who have not seen the proof:

2^p == 1 (mod 2^p-1)
2^pq == (2^p)^q == 1^q == 1 (mod 2^p-1)

Therefore,

2^pq-1 == 1 - 1 == 0 (mod 2^p-1)

I had been taught modular arithmetic long before the age of 16 (as had everyone in my class: do they still teach "clock arithmetic" in UK schools these days?) and the above proof was known to me by the age of 15 or perhaps a year earlier.

Aded in edit: I forgot that you also need to prove that 9 is composite. Most kids aged 8 or over know that 9 = 3*3.

[Uncwilly]

Originally Posted by lukerichards

I'm not sure whether to be pleased or disappointed that, thus far (I haven't finished marking them) they have all used trial division rather than a LL test. Trial division is, of course, the much more efficient way of proving the compositeness of this number!

Meresnne Primes must have a prime exponent, therefore 2⁹-1 can't be prime.

Because the first number that they should try by trial division produces the answer, you should be thrilled. Visually, not 2, 3, or 5. Thus try a few primes (3 to 6 more) quickly. Then maybe switch over. That effectively is how GIMPS handles other numbers.

[lukerichards]

Originally Posted by Uncwilly

Meresnne Primes must have a prime exponent, therefore 2⁹-1 can't be prime.

Whilst I'm aware of this, they are not and I wouldn't expect them to be aware of xilman's proof either, modular arithmetic not being a thing which is taught in schools any more. Even I wasn't taught it and I'm 30 years old.

[R. Gerbicz]

Originally Posted by lukerichards

I'm not sure whether to be pleased or disappointed that, thus far (I haven't finished marking them) they have all used trial division rather than a LL test.

The LLT that I know is applied for odd p prime exponents (https://en.wikipedia.org/wiki/Lucas%...primality_test), so you'd need to extend it to use for composite exponents. In practice ofcourse it would have no value.

[VBCurtis]

Originally Posted by lukerichards

Whilst I'm aware of this, they are not and I wouldn't expect them to be aware of xilman's proof either, modular arithmetic not being a thing which is taught in schools any more. Even I wasn't taught it and I'm 30 years old.

Never mind modular arithmetic: Write 2^9 -1 as 8^3 - 1 and factor as a difference of cubes.

[lukerichards]

Originally Posted by VBCurtis

Never mind modular arithmetic: Write 2^9 -1 as 8^3 - 1 and factor as a difference of cubes.

Also not something they'd have come across in their education yet.

[dcheuk]

Originally Posted by xilman

I did Additional Maths at A Level way back when.

Even faster than trial division is to prove that 2^pq-1 is divisible by both 2^p-1 and 2^q-1, thereby showing that a composite exponent can never yield a Mersenne prime.

To those who have not seen the proof:

2^p == 1 (mod 2^p-1)
2^pq == (2^p)^q == 1^q == 1 (mod 2^p-1)

Therefore,

2^pq-1 == 1 - 1 == 0 (mod 2^p-1)

I had been taught modular arithmetic long before the age of 16 (as had everyone in my class: do they still teach "clock arithmetic" in UK schools these days?) and the above proof was known to me by the age of 15 or perhaps a year earlier.

Aded in edit: I forgot that you also need to prove that 9 is composite. Most kids aged 8 or over know that 9 = 3*3.

If \(n\not\in\text{prime}\) then for any \(a\geq2\) we have \(a^n-1=a^{pq}-1=(a^p-1)\cdot\Big(a^{p(q-1)}+a^{p(q-2)}+\cdots+a^1+1\Big)\).

I wouldn't expect even a college student taking number theory to use Lucas Lehmer to prove 2^p-1 is not prime, they probably won't even remember the lucas lehmer sequence (is that what it is called?).

[xilman]

Originally Posted by lukerichards

Also not something they'd have come across in their education yet.

This thread is leading me to wonder what they have come across in their education.

[lukerichards]

Originally Posted by xilman

This thread is leading me to wonder what they have come across in their education.

I'll post the course spec for GCSE maths and GCSE Additional Maths later. Don't forget they need to cover algebra, number, geometry, statistics and calculus... so depth of study is limited.

[Nick]

If your students are familiar with the formula for summing finitely many terms in a geometric progression, you could show them how that gives
\[ x^{n-1}+x^{n-2}y+x^{n-3}y^2+\ldots +y^{n-1}=\frac{x^n-y^n}{x-y} \]
and deduce for all integers x,y,n with n positive that \(x-y\) divides \(x^n-y^n\).