Number theory · Maths EE idea · Accessible
Divisibility tests in any base
A research question to start from
Which divisibility tests from base 10 have analogues in other bases, and how can a test for divisibility by any integer be constructed?
A starting point, not your question: change the case, the comparison or the limit until it is yours. The research-question builder helps you check it.
Why it works as a maths EE
Familiar ideas generalised: modular arithmetic does all the work, and you can construct new tests and prove them.
Mathematics you would need
- Place-value representation in base b
- Congruences and modular arithmetic
- Orders of elements modulo n
Much of this goes beyond the DP course. That is expected in a maths EE, but you must understand and explain everything you use.
One possible line of attack
- Prove the base-10 tests for 3, 9 and 11 using congruences.
- Generalise to tests for b − 1 and b + 1 in base b.
- Construct and prove tests for 7 and 13 using powers of 10 modulo n.
- Evaluate which tests are practical and why.
Scope and difficulty
Accessible. Accessible; depth comes from the general construction and its efficiency.
Pitfalls
- Listing tests without proofs.
- Too many cases with no general result.
Where to start reading
Search a library catalogue or a university's open lecture notes for: divisibility rules proof congruences; divisibility in base b. Prefer textbooks, lecture notes and journal articles to a single website, and cite everything you use (how to reference a maths EE).