I was writing a coursework piece with the title 'Can primes be described by formulae?' (Anyone else take the IB course?), where I came across the AKS-Test. Essentially, this states that:

For all \(0<k<n, n|^nC_k\) *iff* \(n\) is prime.

Using this fact (and after some modification), the AKS-Test was made by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, which can determine whether an integer is prime or not deterministically and at polynomial time too.

My challenge for you is to prove the above statement.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestHint:

\[k{n\choose k}=n {{n-1}\choose {k-1}}\]

Log in to reply

By Lucas' Theorem, if \(n\) is prime then \(\dbinom{n}{k}\equiv \dbinom{1}{0}\cdot \dbinom{0}{k}\equiv 0\pmod{n}\).

Lucas' Theorem doesn't work for the converse though.

Log in to reply

I never heard of Lucas' Theorem before. Thanks for bringing it to my attention.

Log in to reply