# Congruence of Intergers and modular arthimetic

1. Nov 21, 2009

### doggie_Walkes

Hey im just wondeirng if I have to prove a congruence,

such as

c^3 is congruent to d modulo 7,

where d is set of {0,1 ,7}

So in this problem to prove this example all I need to do is prove that it is a equivalence relation?

So it is reflexsive, symmetric, and transitive?

Is this correct?

2. Nov 21, 2009

### Staff: Mentor

Assuming c is an integer, I believe that what you're trying to prove is that
$$c^3 \equiv 0~mod~7$$
or
$$c^3 \equiv 1~mod~7$$

If so, it's not true. 33 = 27 $\equiv$ 6 mod 7, and 53 = 125$\equiv$ 6 mod 7.

3. Nov 21, 2009

### doggie_Walkes

Thanks mark. I just had a bit of another question if I could ask you ask well?

It just how do i show

b^3 +b^2 +1 does not divide by 5

how do i prove it.

Im thinking this way,
cause i know that b^3 +b^2 +1 is not congruent to 0(mod5)

therefore we use contradition to prove it. im just not sure how to use contradition? or maybe im looking at this in a completely bad light? maybe there is another method?

4. Nov 21, 2009

### HallsofIvy

Staff Emeritus
If you meant "$c^3$ is congruent to one of 0, 1, 6 (mod 7)" then a perfectly valid way to do it is to look at all 7 possibilities: $0^3= 0$, $1^3= 1$, $2^3= 8= 1$, $3^3= 27= 6$, $4^3= 64= 1$, $5^3= 125= 6$, $6^3= 216= 6$, all "mod 7".

5. Nov 21, 2009

### Staff: Mentor

If b^3 + b^2 + 1 is divisible by 5, the ones' digit in b^3 + b^2 + 1 has to be 0 or 5. Another way to say this is that b^3 + b^2 + 1 $\equiv$ 0 mod 5.

Work with the integers modulo 5.
If b $\equiv$ 0 mod 5, then b^3 $\equiv$ 0 mod 5, b^2 $\equiv$ 0 mod 5, so b^3 + b^2 + 1 $\equiv$ 1 mod 5. This means that the ones' digit has to be either 1 or 9.

If b $\equiv$ 1 mod 5, then b^3 $\equiv$ 1 mod 5, b^2 $\equiv$ 1 mod 5, so b^3 + b^2 + 1 $\equiv$ 3 mod 5. This means that the ones' digit has to be either 3 or 8. Because b^3 + b^2 + 1 is always odd, you'll never get an 8 digit in the ones' place, so for this case, the ones' digit has to be 3.

Continue this process for the other three equivalence classes to complete this proof.

6. Nov 27, 2009

### doggie_Walkes

Hey mark, sorry for the late reply,

Im just wondering what you mean by ones' digit

7. Nov 27, 2009

### Staff: Mentor

In the decimal number system, each digit in the numeric representation indicates a power of 10. For example, 435 = 4 * 102 + 3 * 101 + 5 * 100. So 435 is 4 hundreds + 3 tens + 5 ones. The digit in the ones' place is 5 for this number.