Compute the product of the nonzero residues modulo seven. Instead of multiplying 720 directly, pair two with four and three with five, each product being one modulo seven. The remaining residues are one and six, giving product minus one. This is Wilson’s theorem: for an integer n>1, n is prime exactly when (n−1)! is congruent to minus one modulo n. It is a complete criterion, although its direct computation is usually inefficient.
Predict
Predict which part of the argument fails for a composite modulus. A nonzero residue can lack an inverse, and the equation x²=1 can have more than two roots. Modulo eight all four units are self-inverse. Thus the prime proof cannot be transferred merely by replacing the letter p with n. At the same time, discovering a factor is a short certificate of compositeness: checking one exact multiplication proves the conclusion.
Experiment
Compare three different kinds of evidence.
Candidate
Check
What it establishes
7
6!=−1 modulo 7
Prime by Wilson
341
341=11·31
Composite
341
2^340=1 modulo 341
A Fermat pass only
Verify the last row efficiently: 2^10=1024=1 modulo 341, so raise that congruence to 34. A passing test is not a theorem of primality unless its hypotheses and converse justify that conclusion.
Understand
For an odd prime p, every nonzero residue has a unique inverse. Partition them into inverse pairs. A self-inverse element satisfies x²−1=(x−1)(x+1)=0 in a field, hence x=1 or−1. All other pairs contribute one and the two fixed elements contribute−1. For p=2 the statement is checked directly. Conversely suppose n>1 is composite. It has a prime divisor q strictly below n, so q occurs among the factors of(n−1)! and divides that factorial. If the factorial were−1 modulo n, it would also be−1 modulo q, a contradiction. This proves both directions without requiring an algorithm for finding every prime factor of n.
Apply
A stronger certificate can use a known full order. If an integer a has order n−1 modulo n, Lagrange gives n−1≤φ(n), while φ(n)≤n−1. Equality forces n prime. To certify the order, first check a^(n−1)=1 and then check a^((n−1)/q) is not 1 for every prime q dividing n−1. Any proper divisor order would divide one of those exponents. This requires a complete prime factorization of n−1 and a valid unit witness; it is not a free shortcut around all factoring. In contrast, a failed Fermat test for a coprime base proves compositeness, but a pass alone does not.
Continue
For a basic deterministic factoring method, try divisors through floor√n: if n=ab is composite with a, b>1, one factor is at most√n. This proves termination and correctness but says little about practicality for large inputs. More advanced probable-prime and factoring methods have separate guarantees and complexity analyses. In a report, record whether the evidence is a discovered divisor, an exact primality certificate, or a passed screening test. These labels prevent arithmetic experiments from overstating what has been proved.
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
Compute 10! modulo 11.
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
Find gcd(2^5−1, 341).
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
Prove Wilson’s theorem for an odd prime p.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Prove (n−1)!=−1 modulo n implies n is prime for n>1.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Prove 341 passes the base 2 Fermat test despite being composite.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Prove: if a has order n−1 modulo n, then n is prime.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
