0

Show that there is no complete set of representatives for $\mathbb Z/71\mathbb Z$ that includes two of the numbers $1066, 1492$, and $1776$.

My plan is to add the first two representatives of the set [Z=x] and follow through with a basic proof. but not sure how to do this.

kahen
  • 15,760
billy
  • 151
  • 1
    what do all of those numbers have in common (that has to do with mod 71 arithmetic?) –  Jun 30 '13 at 01:43
  • 3
    Consider the pairwise differences. – André Nicolas Jun 30 '13 at 02:05
  • 1
    This means that all of history is a lie... – Brian Rushton Jun 30 '13 at 03:16
  • Please read the tag definition. theorem-provers is about computer theorem proving systems, e.g. Coq. – kahen Jun 30 '13 at 05:23
  • 1
    I'm not sure I like the (implicit) definition being used here. I'd say ${{1,2,3,4,5}}$ is a complete set of representatives for ${\bf Z}/2{\bf Z}$; it's not a reduced system of representatives, it's not a system of distinct representatives, but (I'd say) it's complete. – Gerry Myerson Jun 30 '13 at 05:23

2 Answers2

2

HINT: If $\{r_1,r_2,\dots,r_{71}\}$ is a complete system of representatives for $\Bbb Z/71\Bbb Z$, then $$r_i\not\equiv r_j\pmod{71}$$ whenever $1\le i<j\le 71$.

Brian M. Scott
  • 616,228
1

Sometimes making a question more general makes it easier. I believe this is one of those times, and the specific numbers you have been given have little to do with how one might approach the problem.

First, when you are asked to prove something, you must be sure that you know the definitions of all the terms involved: you should expect to have to use each definition in the course of the proof. So for a positive integer $n$, what is a complete set of representatives modulo n?

I presume that the definition you've been given for this is: a set $S$ of positive integers such that for every integer $0 \leq i < n$, there is exactly one $x \in S$ such that $x \equiv i \pmod{n}$. That is, the residues modulo $n$ of the elements of $S$ are distinct and together they give all possible residues modulo $n$. Note also that if $S$ is a subset of positive integers with distinct residues modulo $n$, then it gives a complete set of representatives modulo $n$ iff there are precisely $n$ elements in $S$.

You are being asked about something one step beyond this definition: under which conditions on a subset $T$ of positive integers can it be enlarged to a set $S$ which is a complete set of representatives modulo $n$? Observe that, again, no two elements of $T$ can have the same residue modulo $n$, since whenever we have distinct integers $x$ and $y$ in $T$ which are congruent modulo $n$, then we will still have $x$ and $y$ in any larger set $S$. Conversely, this is the only thing that can go wrong: if the residues modulo $n$ of the elements of $T$ are distinct, then we can add in one element for each residue class modulo $n$ that we didn't get.

Thus the general solution to a problem of this sort is: a set $T$ of positive integers can be enlarged to a complete set of representatives modulo $n$ if and only if no two distinct elements of $T$ are congruent modulo $n$.

Now we can look at the numbers and see that you are being asked to show that some two of the three numbers $1066$, $1492$ and $1776$ are congruent modulo $71$, i.e., that at least one of $1492-1066$, $1776-1066$ and $1776-1492$ is divisible by $71$. That's easy...

Pete L. Clark
  • 97,892