Skip to content

11.20 Partition

  1. Calculate the remainder of \(x\) divided by \(n\):

    1. \(x = 3 \cdot 11 \cdot 17 \cdot 71 \cdot 101\), \(n = 5, \ 7\)

    2. \(x = \sum_{i=0}^{100} i!\), \(n = 50\)

      For \(i \geq 10\), \(i! \equiv 0 \pmod{50}\) (because \(i! = 5 \cdot 10 \cdot \ldots\)).

      \(5! \equiv 20 \pmod{50}\) \(6! \equiv 20 \cdot 6 \equiv 20 \pmod{50}\) \(7! \equiv 20 \cdot 7 \equiv 40 \pmod{50}\) \(8! \equiv 40 \cdot 8 \equiv 40 \pmod{50}\)

  2. List the ordered pairs in the equivalence relation on \(A = \{1, 2, 3, 4, 5\}\) associated with the partition \(\{\{1,2\},\{3,4,5\}\}\):

    \(\mathcal{R}=\{(1,1),(2,2),(3,3),(4,4),(5,5),(1,2),(2,1),(3,5),(5,3),(3,4),(4,3),(4,5),(5,4)\}\)​

  3. Show that the relation \(R\) on \(\mathbb{N}\) given by \(aRb\) if \(b = 2^k \cdot a\) for some \(k \in \mathbb{N}_0\) is a partial ordering.

    • Reflexive: \(aRa\) because \(a = 2^0 \cdot a\).
    • Antisymmetric: If \(aRb\) and \(bRa\), then \(b = 2^k \cdot a\) and \(a = 2^r \cdot b\) for \(k, r \in \mathbb{N}_0\). Substituting \(b\) in \(a = 2^r \cdot (2^k \cdot a)\), we get \(a = 2^{k+r} \cdot a\). Dividing through by \(a\), we have \(1 = 2^{k+r}\). This is only possible if \(k + r = 0\), which implies \(k = r = 0\). Hence, \(b = 2^0 \cdot a = a\).
    • Transitive: If \(aRb\) and \(bRc\), then \(b = 2^k \cdot a\) and \(c = 2^r \cdot b\) for \(k, r \in \mathbb{N}_0\). Substituting \(b\), we get \(c = 2^r \cdot (2^k \cdot a) = 2^{k+r} \cdot a\). Since \(k, r \in \mathbb{N}_0\), it follows that \(k + r \in \mathbb{N}_0\). Therefore, \(aRc\).

    So by definition, this is a partial order relation.

  4. Show that the relation \(R\) on \(\mathbb{R} \times \mathbb{R}\) given by: \((a, b)R(x, y)\) if \(a \leq x\) and \(b \leq y\) is a partial ordering.

    Let \(R_1\) be an order relation on \(A\). Let \(R_2\) be an order relation on \(B\).

    Let \(R\) be this relation: \((a, b)R(x, y)\) iff \(a \,R_1\, x\) and \(b \,R_2\, y\).

    \(\therefore R\) is an order relation.