Congruence of Intergers and modular arthimetic

**doggie_Walkes** · Nov21-09, 11:14 AM

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?

**Mark44** · Nov21-09, 12:47 PM

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

If so, it's not true. 3³ = 27 $LaTeX Code: \\equiv$ 6 mod 7, and 5³ = 125 $LaTeX Code: \\equiv$ 6 mod 7.

**doggie_Walkes** · Nov21-09, 01:16 PM

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?

**HallsofIvy** · Nov21-09, 01:21 PM

If you meant "

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:

,

,

,

,

,

,

, all "mod 7".

**Mark44** · Nov21-09, 01:53 PM

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 $LaTeX Code: \\equiv$ 0 mod 5.

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

If b $LaTeX Code: \\equiv$ 1 mod 5, then b^3 $LaTeX Code: \\equiv$ 1 mod 5, b^2 $LaTeX Code: \\equiv$ 1 mod 5, so b^3 + b^2 + 1 $LaTeX Code: \\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.

**doggie_Walkes** · Nov27-09, 11:11 AM

Hey mark, sorry for the late reply,

Im just wondering what you mean by ones' digit

**Mark44** · Nov27-09, 01:29 PM

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