Test question
 

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:

[QUOTE]
Mersenne primes are prime numbers that can be written in the form [TEX]2^n-1[/TEX] where n is a whole number.

For example, 3 can be written as [TEX]2^2-1[/TEX]

Prove that [TEX]2^9-1[/TEX] is [b]not[/b] a Mersenne prime.
[/QUOTE]

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!

[QUOTE=lukerichards;515418]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![/QUOTE]
I did Additional Maths at A Level way back when.

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

To those who have not seen the proof:[INDENT]2[SUP]p[/SUP] == 1 (mod 2[SUP]p[/SUP]-1)
2[SUP]pq[/SUP] == (2[SUP]p[/SUP])[SUP]q[/SUP] == 1[SUP]q[/SUP] == 1 (mod 2[SUP]p[/SUP]-1)[/INDENT]Therefore,[INDENT]2[SUP]pq[/SUP]-1 == 1 - 1 == 0 (mod 2[SUP]p[/SUP]-1)[/INDENT]
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.

[QUOTE=lukerichards;515418]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![/QUOTE]Meresnne Primes must have a prime exponent, therefore 2[SUP]9[/SUP]-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.

[QUOTE=Uncwilly;515428]Meresnne Primes must have a prime exponent, therefore 2[SUP]9[/SUP]-1 can't be prime.
[/QUOTE]

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.

[QUOTE=lukerichards;515418]
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.[/QUOTE]

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

[QUOTE=lukerichards;515429]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.[/QUOTE]

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

[QUOTE=VBCurtis;515436]Never mind modular arithmetic: Write 2^9 -1 as 8^3 - 1 and factor as a difference of cubes.[/QUOTE]

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

[QUOTE=xilman;515427]I did Additional Maths at A Level way back when.

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

To those who have not seen the proof:[INDENT]2[SUP]p[/SUP] == 1 (mod 2[SUP]p[/SUP]-1)
2[SUP]pq[/SUP] == (2[SUP]p[/SUP])[SUP]q[/SUP] == 1[SUP]q[/SUP] == 1 (mod 2[SUP]p[/SUP]-1)[/INDENT]Therefore,[INDENT]2[SUP]pq[/SUP]-1 == 1 - 1 == 0 (mod 2[SUP]p[/SUP]-1)[/INDENT]
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.[/QUOTE]

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?).

[QUOTE=lukerichards;515437]Also not something they'd have come across in their education yet.[/QUOTE]This thread is leading me to wonder what they have come across in their education.

[QUOTE=xilman;515466]This thread is leading me to wonder what they have come across in their education.[/QUOTE]

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.

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\).