Suppose \(a\) and \(b\) are integers such that \(a \equiv 11
\pmod{17}\text{,}\) and \(b \equiv 3 \pmod{17}\text{.}\) Find the integer \(c\) with \(0\leq c\leq 16\) such that satisfies these.
Let \(a, b, c\) be integers, where \(a, b \neq 0\text{.}\) Follow the steps below to prove that if \(a \mid b\) and \(b \mid c\text{,}\) then \(a \mid
c\text{.}\)
First, we recognize what we want to prove is in the form “if \(p\text{,}\) then \(q\text{.}\)” What is hypothesis \(p\text{?}\) What is the conclusion \(q\text{?}\)
When we want to prove a statement of the form “if \(p\text{,}\) then \(q\)” directly, we assume \(p\) is true and try to show \(q\text{.}\) This is commonly where we set some notation, for example, Suppose \(a,b,c\) are integers such that \(a \mid b\) and \(b \mid c\text{.}\)
Next we need to recall what \(x \mid y\) or divides means. It should have something to do with the existence of an integer. We say \(x \mid y\) or \(x\) divides \(y\) if there exists an integer \(k\) such that
Check back above to be sure that the two integers whose existence is guaranteed have different names. They need different names because they need not be the same integer.
Now look back to the goal \(q\) that we set above. We should have something like “\(a \mid c\)”. Use the definition to re-express this goal. We want to show there exists an integer … such that ….
Now use the two equations from (d) to produce the integer whose existence we want from (f). Use equations or complete sentences. Don’t just write sentence fragments of expressions.
Follow the steps below to prove that \(n^3 -n\) is divisible by \(3\) for every integer \(n\text{.}\)
Remember that divisibility statements can be rewritten as congruence conditions. e.g., \(a\) is divisible by \(b\) can be written as \(a \equiv 0 \pmod{b}\text{.}\) What is the congruence condition for this problem?
Rewrite the above, alerting the proof reader that our statement is equivalent to the desired statement. Be sure to specify that we will show it for every integer \(n\text{.}\) e.g., It suffices to show … for every …
For each case, write down the assumption that \(n\) is in the congruence class under consideration. Use properties of modular arithmetic from class to prove the result in that case. Repeat for each case.
Let \(a, b, c, d, m\) be integers, with \(m \gt 1\text{.}\) Follow the steps below to prove that if \(a \equiv b \pmod{m}\) and \(c \equiv d
\pmod{m}\text{,}\) then \(a + c \equiv b + d \pmod{m}\text{.}\)
First, recognize what we want to prove is in the form “if \(p\text{,}\) then \(q\text{.}\)” What is \(p\text{?}\) What is \(q\text{?}\)
As before, to prove a statement of the form “if \(p\text{,}\) then \(q\)” directly, we assume \(p\) is true and try to show \(q\text{.}\) This is commonly where we set some notation as well. Suppose …. We want to show ….
Above are some statements about congruences. Use the definition or theorems to state our assumption and our goal in terms of divisibility or existence of integers.
Find a counterexample to the following statement about congruences.
Let \(a\text{,}\)\(b\text{,}\)\(c\text{,}\) and \(m\) be integers with \(m \gt 2\text{.}\) If \(ac \equiv bc \pmod{m}\text{,}\) then \(a \equiv b \pmod{m}\text{.}\)
