Carmichael Function Divisibility Search

ISEF Category: Mathematics

Subcategory: Number Theory  ·  Difficulty: Advanced  ·  Setup: University Lab  ·  Time: Full Year

The Hook

Some number theory questions hide in plain sight. This one asks whether a special divisibility rule can hold for composite numbers that are not Carmichael numbers. You are not just checking examples, you are hunting for a pattern, or a counterexample, using math and computation together.

What Is It?

The Carmichael function, written λ(n), tells you the size of the smallest exponent that works for every number coprime to n. Think of it like the least common rhythm shared by the multiplicative parts of n. In this project, you test whether λ(n) can divide n - 1 for composite n outside the known Carmichael-number family.

That sounds abstract, but the idea is simple. You are asking whether a composite number can fake a prime-like property in a new way. If a prime p divides p - 1 in the obvious sense only for p = 2, composite numbers have to work much harder to satisfy λ(n) | n - 1. That makes the search both narrow and deep.

Why This Is a Good Topic

This is a strong science fair topic because you can turn a pure math question into a clear computational search. You can test many candidates, filter them with number theory rules, and measure how far the search goes before the pattern fails. The real-world skill is algorithmic thinking, because you must design a sieve that removes impossible cases fast. You can learn proof structure, modular arithmetic, and how to justify a negative result carefully.

Research Questions

• How does restricting n to specific residue classes change the number of candidates that survive the sieve?
• What is the effect of adding prime-factor constraints on the search space for λ(n)
• n - 1?
• Does every composite n below a chosen bound fail the condition outside the Carmichael family?
• To what extent can a residue-class sieve reduce the time needed to test candidates below 10^14?
• Which prime-factor patterns appear most often among composite numbers that come closest to satisfying λ(n)
• n - 1?
• How does the density of surviving candidates change when you require more distinct prime factors?

Basic Materials

• Laptop or desktop computer with enough storage for large integer data
• Python installed with SymPy or SageMath support
• Spreadsheet software for logging candidate counts
• External hard drive or cloud storage for search outputs
• Notebook for proof notes and sieve logic
• Reliable internet access for reading papers and checking sequences.

Advanced Materials

• University or lab workstation with high RAM and fast disk access
• SageMath, PARI/GP, or Mathematica for integer arithmetic and factorization
• Python with multiprocessing for distributed search
• Access to a computer cluster or multiple cores for parallel sieving
• Journal access for reading prior work on Carmichael numbers and Lehmer-type problems
• Version control system for tracking code changes and search results.

Software & Tools

• Python: Runs the main search, applies modular filters, and records survivors.
• SageMath: Handles fast integer arithmetic, factorization, and Carmichael function checks.
• PARI/GP: Tests large-number properties quickly and helps compare against SageMath output.
• Jupyter Notebook: Keeps your code, notes, and result tables in one place.
• ImageJ: Not needed for this topic, so skip it unless you are visualizing unrelated data.

Experiment Steps

1. Define the exact search question and the numeric bound you will test.
2. Build the mathematical filters that remove impossible composite numbers before full checking.
3. Organize the candidate list by residue class and prime-factor structure.
4. Write code to compute λ(n) and test the divisibility condition on surviving candidates.
5. Compare the sieve's speed and coverage against a direct brute-force baseline.
6. Summarize whether the search found any examples, and if not, how much of the space you ruled out.

Common Pitfalls

• Confusing λ(n) with Euler's totient function φ(n), which changes the whole search target.
• Using a brute-force scan without sieving, which makes the computation too slow to finish.
• Testing candidates without verifying that factorization is complete, which can give false positives.
• Losing track of which residue-class filters were applied, which makes the result hard to defend.
• Claiming a proof of nonexistence when your code only checked a finite bound, which overstates the result.

What Makes This Competitive

A strong version of this project does more than list checked numbers. It explains the sieve, proves why each filter is valid, and measures how much work each filter saves. You can raise the level by comparing multiple search strategies, analyzing candidate density, or proving new partial exclusions for special residue classes. Clear code, careful math, and a clean boundary between computation and proof matter a lot here.

Project Variations

• Test the same λ(n)
• n - 1 condition only on squarefree composite numbers to see whether the sieve gets stronger.
• Compare residue-class sieves for numbers with two prime factors versus three or more prime factors.
• Search a smaller bound, then analyze which modular patterns suggest the best path to a larger computation.

Learn More

• Wikipedia: The entry on the Carmichael function gives a quick overview of λ(n) and related definitions.
• OEIS: Search for sequences related to Carmichael numbers, Lehmer's totient problem, and function values of λ(n).
• MIT OpenCourseWare: Search for number theory lecture notes that cover modular arithmetic, multiplicative functions, and prime factorization.
• PubMed: Not relevant for this topic, so use other math sources instead.
• MathSciNet or zbMATH Open: Search for review articles and papers on Carmichael numbers and Lehmer-type conjectures.