Waste less time on Facebook — follow Brilliant.
Back to all chapters

Greatest Common Divisor / Lowest Common Multiple

What is the largest number that can divide two numbers without a remainder? What is the smallest number that is divisible by two numbers without a remainder?

Greatest Common Divisor / Lowest Common Multiple: Level 4 Challenges


Consider the sequence \( 50 + n^2 \) for positive integer \(n\):

\[51, 54, 59, 66, 75, \ldots\]

If we take the greatest common divisor of 2 consecutive terms, we obtain

\[3, 1, 1, 3, \ldots\]

What is the sum of all distinct elements in the second series?

Find the sum of all integers \(k\) with \(1\leq k\leq 2015\) and \(\gcd(k,2015)=1\).

Let \(m\) and \(n\) be positive integers such that 11 divides \(m+13n\) and 13 divides \(m+11n\).

What is the minimum value of \(m+n\)?

\[ \text{lcm}(1,77) + \text{lcm}(2,77) + \text{lcm}(3,77) + \cdots + \text{lcm}(77,77) = \, ? \]

Notation: \(\text{lcm}(a,b) \) denote the Lowest Common Multiple of \(a\) and \(b\).

\[\large\underbrace{0,1,0,1,0,0,0,1,0,1}_{\text{period}}, 0,1,0,1,0,0,0,1,0,1,0,\dots\] Let \(n\) be a positive integer, and let the function \(f_n:\ \mathbb N \to \{0,1\}\) be defined by \[f_n(m) = \begin{cases} 0 & \gcd(n,m) > 1 \\ 1 & \gcd(n,m) = 1. \end{cases}\] That is, \(f_n(m)\) tells us whether \(m\) is coprime to \(n\) or not. If we write out the values of \(f_n,\) we get a periodic (repeating) pattern. For instance, the list above gives the values of \(f_{10}\) starting at \(m = 0\); the pattern repeats itself with period 10.

Consider the function \(f_{1400}\). What is its period?

Note: The period is defined as the smallest possible value, that is, the least positive \(T\) such that \(f_n(m + T) = f_n(m)\) for all integers \(m\).


Problem Loading...

Note Loading...

Set Loading...