If \(x^2 = x + 1\), then \(x = 1 + \sqrt{5}\) or \(x = 1 - \sqrt{5}\)

Prove the following: If \(x^3\) is irrational then \(x\) is irrational.

Let \(n = ab\) be the product of positive integers \(a\) and \(b\). Prove that either \(a \leq \sqrt{n}\) or \(b \leq \sqrt{n}\).

Show that \( (p \to q) \to r\) is not logically equivalent to \( p \to (q \to r)\)

Simplify the following if possible: \( (p \to (q \to r)) \to ((p \to q) \to (p \to r))\)

Let \(a\) be an integer. Prove that there exists an integer \(k\) such that \(a^2 = 3k\) or \(a^2 = 3k + 1\).

Let \(x,a\) be integers with \(a \geq 2 \) such that \(a \mid 11x + 3\) and \(a \mid 55x + 52\). Find \(a\).

Tell me how many natural numbers \( 1 \leq k \leq 14\) smaller than 15 have the following property \( \gcd{(k, 15)} = 1 \). Just for your information, we say two numbers \(a, b\) are relatively prime when \( \gcd{(a,b)} = 1\). Also (for your information only) the number of relatively prime natural numbers smaller than \(a\) is called \( \phi(a) \) the Euler Totient Function. So this question is asking you to calculate \(\phi(15)\).

Determine whether 9833 is prime.

Show that for every natural number \(k\), \(6^k\) will never end in a 0 (using a decimal representation).

Prove that \( 6 | n^3 + 5n\) for all \( n \geq 1 \)

Find a (closed-form) formula for the following sum: $$ (0 - 0) + (1 - 1) + (8-4) + (27-9) + \cdots + (n^3 - n^2) $$ Use induction to prove your result.

Find this sum: $$ S = -56 - 49 - 42 - \cdots + 623 + 630 + 637 $$

Which, if any, of the following three sets are equal? $$ A = \{ k \mid k \in \mathbb{N}, 3 \nmid k, k \leq 12 \} $$ $$ B = \{ 3k + 1 \mid k \in \mathbb{N}, k \leq 4 \} $$ $$ C = \{ k \mid k \in \mathbb{N}, \gcd{(k, 3)}=1, k \leq 11 \} $$

Given the set \(A = \{1, 2, 3\}\) create a binary relation on \(A\) (that is, a subset of \(A \times A\)) which is reflexive,symmetric, and is not transitive

Prove that \(\overline{a} + \overline{b} = \overline{a+b}\) where \(\overline{a}\) is the equivalence class of \(a\) under the relation on \(\mathbb{Z}\) given by \(x \sim y\) when \(p | (x-y)\). Here \(\overline{a} + \overline{b}\) means the set \(\{ x + y \mid x \sim a \land y \sim b \}\), made by summing anything in \(\overline{a}\) and anything in \(\overline{b}\). This is an elaborate way of asking if computing \( (a + b) \textrm{ mod } p = (a \textrm{ mod } p) + (b \textrm{ mod } p) \).

None, happy spring break.

Let \(S = \{ 1,2,3,4\}\) and \(f,g : S \to S\) by \(f = \{(1,3),(2,2),(3,4),(4,1)\}\) and \(g = \{(1,4), (2,3), (3,1), (4,2)\}\). Find \(g \circ f \circ g^{-1} \).

Find \(x\) such that \(79x \equiv 15 \mod{ 722 }\)

Find \(6^{128} \mod{ 13 }\)

Problem 5 from math.prof.ninja/417, the in-class problems from Friday.

Problem 8 from math.prof.ninja/420, the in-class problems from Monday.

Problem 6 from math.prof.ninja/422

The last problem from 424

Give a method for detecting if a graph is bipartite.

How many 6 digit integers have 1 digit repeated 3 times, another distinct digit repeated twice, and a third digit? For instance 292129 or 877666.

Prove that the Petersen graph is not Hamiltonian

Create a graph in which any walk on the graph of length \(k\) is a length \(k\) word made from 'a' and 'b' with at most two 'b's in a row. Use this graph to decide the number of words of length 4 with this property.

Problem 4 from Monday's problem set

What is the worst case complexity of insertion sort?

Make a list of the super-powers you developed (or are developing) in this class.