Math IOQM

Q. Find the number of values of \( n \in \mathbb{N} \), such that that the largest exponent of 2 dividing \( n! \) equals \( n \). 1. The Formula Legendre's Formula states that the largest exponent of a prime \( p \) dividing \( n! \) (denoted as \( v_p(n!) \)) is given by: \[ v_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor \] An alternative and very useful form of this formula relates the exponent to the sum of the digits of \( n \) when written in base \( p \): \[ v_p(n!) = \frac{n - s_p(n)}{p - 1} \] where \( s_p(n) \) is the sum of the digits of \( n \) in base \( p \). 2. Solving the Problem The problem asks for the number of values of \( n \in \mathbb{N} \) such that \( v_2(n!) = n \). Step 1: Apply the formula for \( p = 2 \) Using the second form of Legendre's Formula: \[ v_2(n!) = \frac{n - s_2(n)}{2 - 1} = n - s_2(n) \] Step 2: Set up the equation According to the problem statement, we need \( v_2(n!) = n \). Substituting our formu...

The proof for the formula of Euler’s Totient Function, denoted as \( \phi(n) \), relies on two primary properties: the behavior of the function on prime powers and its multiplicative nature. The goal is to prove that for a positive integer \( n \) with prime factorization \( n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} \): \[ \phi(n) = n \prod_{i=1}^{k} \left( 1 - \frac{1}{p_i} \right) \] Step 1: \( \phi(n) \) for Prime Powers Let \( p \) be a prime number and \( n = p^k \). To find \( \phi(p^k) \), we count how many integers between 1 and \( p^k \) are not coprime to \( p^k \). An integer is not coprime to \( p^k \) if and only if it is a multiple of \( p \). The multiples of \( p \) in the range \( [1, p^k] \) are: \[ p, 2p, 3p, \dots, (p^{k-1})p \] There are exactly \( p^{k-1} \) such multiples. Subtracting these from the total count: \[ \phi(p^k) = p^k - p^{k-1} = p^k \left( 1 - \frac{1}{p} \right) \] Step 2: The Multiplicative Property A key property of the Totient functio...

To prove that Euler's totient function \( \phi(n) \) is multiplicative—meaning that if \( \gcd(a,b) = 1 \), then \( \phi(ab) = \phi(a)\phi(b) \)—we can use a structural approach involving a rectangular array of integers. 1. Setting up the Array Recall that \( \phi(n) \) is the number of integers \( x \) such that \( 1 \le x \le n \) and \( \gcd(x,n) = 1 \). Let \( n = ab \) with \( \gcd(a,b) = 1 \). We can list the integers from 1 to \( ab \) in an \( a \times b \) matrix: \[ \begin{array}{cccc} \text{Col 1} & \text{Col 2} & \cdots & \text{Col } k \\ 1 & 2 & \cdots & k \\ b+1 & b+2 & \cdots & b+k \\ 2b+1 & 2b+2 & \cdots & 2b+k \\ \cdots & \cdots & \cdots & \cdots \\ (a-1)b+1 & (a-1)b+2 & \cdots & (a-1)b+k \end{array} \] 2. Row and Column Conditions For an element \( x \) in this table to be counted in \( \phi(ab) \), it must satisfy \( \gcd(x,ab) = 1 \). This is equivalent to: 1. \( \gcd(x,b) = 1 ...

Bézout’s Identity Bézout’s identity states that for any two integers \( a \) and \( b \), not both zero, there exist integers \( x \) and \( y \) such that: \[ ax + by = \gcd(a, b) \] In other words, the greatest common divisor of \( a \) and \( b \) can be expressed as a linear combination of \( a \) and \( b \). The identity follows from Euclid’s algorithm and can be obtained by working backwards through the division steps. The Process to find integers \( x \) and \( y \): 1. Apply Euclid’s algorithm to compute \( \gcd(a, b) \). 2. Write each remainder as a combination of the previous two numbers. 3. Substitute backward until the GCD is written in the form \( ax + by \). Example: \( \gcd(252, 105) \) From Euclid’s algorithm: \[ 252 = 105 \times 2 + 42 \] \[ 105 = 42 \times 2 + 21 \] \[ 42 = 21 \times 2 + 0 \] Thus, \( \gcd(252, 105) = 21 \). Now work backwards: \[ 21 = 105 - 42 \times 2 \] \[ 42 = 252 - 105 \times 2 \] Substitute: \[ 21 = 105 - 2(252 - 105 \times 2...

6.2 Euclid’s GCD Algorithm Euclid’s algorithm is an efficient method for computing the greatest common divisor of two integers. It is based on the principle that the GCD of two numbers does not change if the larger number is replaced by its difference with the smaller number. The Division Lemma. For any two integers \( a \) and \( b \) (where \( b \neq 0 \)), there exist unique integers \( q \) and \( r \) such that: \[ a = bq + r, \quad 0 \le r

 1. GCD is the largest positive integer(with one exception) that divides each of the integers in a given set. 2. Even if one or more input numbers are negative, output is always positive. 3. Both inputs/output are integers. 4. gcd(a,0) = |a| 5. gcd(0,0) = 0, this is defined like this. Though gcd(0,0) can be any integer. This is the only case where gcd is not positive. It is 0.