Divisors

Counting and listing divisors from the prime factorisation.

If n = p₁ᵃ · p₂ᵇ · …, then every divisor picks an exponent between 0 and a for p₁, between 0 and b for p₂, and so on, which is why the number of divisors is (a+1)(b+1)…. Perfect squares are exactly the numbers with an odd count.

Àwọn ààtò àwọn ìṣàmúlò-ètò · divisors of 36

Number-Theory · Divisors

Divisors of 36

Àwọn ìṣàmúlò-ètò

36 = 2^{2} \times 3^{2}
Prime-factorise first.
d(n) = (2+1) \cdot (2+1) = 9
Each divisor picks an exponent from 0 up to the prime's exponent, so multiply (exponent + 1) for each prime.
1, 2, 3, 4, 6, 9, 12, 18, 36
List them in increasing order.

Fi àwọn àgbèwọlé hàn

1, 2, 3, 4, 6, 9, 12, 18, 36

Nígbà yìí Yan àwọn àkóónú kan, tàbí tẹ̀ àtí kọ́ àwọn àkóónú rẹ̀. Àwọn ìṣàmúlò-ètò gbogbo, àwòrán, àwọn à

Fi iṣẹ́ rẹ̀ pamọ́

A free account adds notes on every lesson, a record of what you have finished, your solved problems in one place, and a tutor you can ask about this page. The maths itself is open to everyone, signed in or not.

Fikún Àwọn Ìṣàmúlò-ètò

Àwọn àmì-ìwé tí a lo níbẹ̀

Tẹ àwọn àmì-ìwé fún ìṣàfarawé fún àwọn ìṣàmúlò-ètò, àwòrán, àti àwọn àmì-ìwé àwọn àmì-ìwé.

Bii o ṣe le: Divisors

Prime-factorise first.
Each divisor picks an exponent from 0 up to the prime's exponent, so multiply (exponent + 1) for each prime.
List them in increasing order.

Àwọn Àtòjọ-ẹ̀yàn

Why are primes so important?

Every integer factors into primes in exactly one way, so primes are the atoms of multiplication. Cryptography relies on that factoring being easy to state and hard to do.

How do I tell whether a big number is prime?

Trial division up to the square root works for small numbers. For large ones, probabilistic tests (Miller-Rabin) give an answer that is wrong with negligible probability, and deterministic tests (AKS) exist but are slower.

Diẹ̀ nínú Number Theory

Prime factorisation Prime numbers GCD and LCM Modular arithmetic Sequences Number bases Diophantine equations Fermat's little theorem and Euler's theorem RSA: cryptography from number theory