常用整数整除判定定理有哪些？除经典定理外还有哪些实用定理？

Great question! The theorems you named are core tools for integer divisibility, but there are plenty of other practical and foundational rules/theorems that come up constantly—whether you're doing quick mental checks or working through formal number theory proofs. Let's break them down:

These are the quick, intuitive rules you might have picked up early on, perfect for small divisors:

• Divisibility by 2 or 5: A number is divisible by 2 if its last digit is even; divisible by 5 if its last digit is 0 or 5. No fancy math needed here—just a glance at the end digit.
• Divisibility by 4 or 25: Check the last two digits of the number. If that two-digit number divides evenly by 4 (or 25), the whole number does too. This works because 100 is a multiple of both, so higher digits don't affect the divisibility.
• Divisibility by 8 or 125: Similar to the above, but look at the last three digits. Since 1000 is divisible by 8 and 125, only the final three digits matter for this check.
• Divisibility by 3 or 9: Sum up all the digits of the number. If the total is divisible by 3 (or 9), then the original number is too. This comes from the fact that 10 ≡ 1 mod 3 and 10 ≡ 1 mod 9, so each digit's place value is equivalent to 1 times the digit itself modulo those numbers.
• Divisibility by 11: Alternately add and subtract digits from left to right. If the result is 0 or a multiple of 11, the number is divisible by 11. For example, take 1331: 1 - 3 + 3 - 1 = 0, so it's divisible by 11. This works because 10 ≡ -1 mod 11, so each digit alternates sign in the modulo calculation.
• Composite divisors: If a composite number n factors into coprime integers a and b (meaning gcd(a,b)=1), then a number is divisible by n if and only if it's divisible by both a and b. For example, to check divisibility by 6, just confirm the number is even (divisible by 2) and its digit sum is a multiple of 3.

You mentioned Fermat's Little Theorem, but Euler's Theorem expands this to work with any pair of coprime integers. It states: if gcd(a, n) = 1, then a^φ(n) ≡ 1 mod n, where φ(n) is Euler's totient function (count of integers ≤n that share no common factors with n). This is incredibly useful for simplifying large exponents when checking divisibility. For example, to see if 7 divides 3^100: since φ(7)=6, 3^6 ≡ 1 mod7, so 3^100 = 3^(6×16 + 4) = (3^6)^16 × 3^4 ≡ 1^16 × 81 ≡ 81 mod7 ≡4 mod7≠0—so 7 does not divide 3^100.

This is a foundational theorem that's key for proving divisibility results and solving linear equations with integers. It says: if gcd(a, b) = d, then there exist integers x and y such that ax + by = d. A critical corollary here is: an integer c is divisible by d (the gcd of a and b) if and only if c can be written as a linear combination of a and b. Another useful result from this: if a divides bc and gcd(a,b)=1, then a must divide c. This comes up all the time in number theory proofs.

These are handy shortcuts for problems involving exponents:

• For any positive integer k, n^k - m^k is divisible by n - m. For example, 10^4 - 3^4 is divisible by 10-3=7—no need to calculate the whole number to confirm.
• If k is odd, n^k + m^k is divisible by n + m. So 5^3 + 2^3 is divisible by 5+2=7, which checks out (125+8=133, and 133/7=19).

CRT helps break down divisibility checks for large composite numbers into smaller, easier ones. If n factors into prime powers like n = p₁^k₁ × p₂^k₂ × ... × pᵣ^kᵣ, then a number is divisible by n if and only if it's divisible by each pᵢ^kᵢ individually. Even for smaller composites, this is useful: checking divisibility by 12 is the same as checking divisibility by 4 and 3 (since they're coprime), which is way simpler than dividing by 12 directly.

While it's primarily a primality test, Wilson's Theorem can be used for specific divisibility checks. It states: a positive integer p is prime if and only if (p-1)! ≡ -1 mod p. So, for example, to check if 7 divides 6! + 1: since 7 is prime, 6! ≡ -1 mod7, so 6! +1 ≡0 mod7—meaning yes, 7 divides it. It's not a general-purpose rule, but it's a fun tool for niche divisibility problems.

内容的提问来源于stack exchange，提问作者mick