Let m, n be natural numbers such that their greatest common
divisor gcd(m, n) = 1. Prove that there is a natural number k such
that n divides ((m^k) − 1).
Show the following identities for a, b, c ∈ N.
(a) gcd(ca, cb) = c gcd(a, b) Hint: To show that two integers x,
y ∈ Z are equal you can show that both x | y and y | x which
implies x = y or x = −y. Thus, if both x and y have the same sign,
they must be equal.
(b) lcm(ca, cb) = c lcm(a, b)
(c) ab = lcm(a, b) gcd(a, b) Hint: Consider...
(1) Show that the set { 1 m + 1 n : m, n ∈ N} is countable.
(2) Show that the set {a + b √ 2 : a, b ∈ Q} is countable.
(3) Show that the intersection of two countable sets is
countable.
(4) Show that the set of all irrational numbers is
uncountable.
(5) Let C = {0, 1, 2, . . . , 9}. Show that the set C ×C × · · ·
is...
1- Show that (n^3+3n^2+3n+1) / (n+1) is O (n2 ). Use the
definition and proof of big-O notation.
2- Prove using the definition of Omega notation that either 8 n
is Ω (5 n ) or not.
please help be with both
There are (m − 1)n + 1 people in a room. Show that either there
are m people who mutually do not know each other, or there is a
person who knows at least n others.
i
need a very detailed proof
(Show
your work!)
Let n
> 1. Prove: The sum of the positive integers less than or equal
to n is a divisor of the product of the positive integers less than
or equal to n if and only if n + 1 is composite.