# Homework Help: Modular Arithemetic Question

1. Feb 18, 2012

### trap101

For n in N (Natural Numbers), use modular arithemetic to establish each of the following divisibility statements:

a) 7 | 52n + 3 (25n - 2)

Attempt: Well I've set up a mod 7 table and was figuring out the values from n = 0,....6 for the two individual expressions, then I was going to combine them. But I of course hit a rough patch when I got to 25n - 2. Since I'm in the Natural numbers, fractions do not exist, so how do I treat 25n - 2 when n = 0 ?

2. Feb 18, 2012

### tiny-tim

hi trap101!
some people include 0 in the natural numbers, and some don't

clearly, this question doesn't

see http://en.wikipedia.org/wiki/Natural_numbers#Notation for a discussion

3. Feb 18, 2012

### trap101

ahh this is true. I gather you would deduce this from the fact that I would have been stuck with a fraction if n = 0 did exist? So if n = 0 was included in the natural numbers for this question, would the question even be answerable?

4. Feb 19, 2012

### alanlu

7 is a prime number, so Z7 is a finite field, and each non-zero element thus has a multiplicative inverse. You would treat 2-2 as 4 * 4 mod 7 in this case.

Last edited: Feb 19, 2012
5. Feb 19, 2012

### trap101

ok thanks

6. Feb 24, 2012

### trap101

I had another quick question pertaining to this sort of question. The question asked me to establish that the above expression is true. Is the only way I can establish its truth by using a mod table or is there another method?

7. Feb 24, 2012

### alanlu

Last edited: Feb 24, 2012
8. Feb 24, 2012

### Deveno

you shouldn't have to use a table.

52n = (52)n, whether mod 7 or not.

but mod 7, we can reduce 52 = 25 to 4. that is:

52n = 4n (mod 7).

now 3(25n-2) = 3(25)n(2-2).

reduce everything on the right you can mod 7,

you will have (3)(somethingn)(42) (mod 7).

if you did everything right, you should be able to add the terms and it will be obvious what you have is equal to 0 mod 7, thus proving the orginial statement.

9. Feb 25, 2012

### trap101

Thanks. I got an answer, but my approach was a long winded table. Now I was trying to reduce how you suggested and I got (3)(4n 42 (mod 7).

I made bold the 42 because I don't see where you got that from, as well what happened to the 2-2 portion?

Now adding up these congruences I got 4n(1 + 19)....should that have been 4n(1+20), to get 21 and thus proving divisibility by 7?

10. Feb 26, 2012

### Deveno

mod 7, we have:

(2)(4) = 8 = 1 (mod 7).

therefore 2-1 = 4

4 is the ONLY number x in {1,2,3,4,5,6} with this property: 2x = 1 (mod 7), which you may check if you like. it therefore makes sense to speak of 4 as THE inverse for 2 (mod 7).

so if 2-1 = 4 (mod 7)

then 2-2 = (2-1)2 = 42 (mod 7).

it may come as no surprise that we can "multiply mod n". what IS no doubt surprising, is sometimes, we can also "divide mod n".

in fact, if n is prime (as 7 so conveniently happens to be), we can divide by any non-zero residue class. that is, the integers modulo p (where p is prime) form a FIELD.

mod 7 we have:

1-1 = 1
2-1 = 4
3-1 = 5
4-1 = 2
5-1 = 3
6-1 = 6.

now, to finish "my approach" what is 16 (mod 7), and therefore, what is (3)(42) (mod 7)?