Modular Arithmetic: Divisibility Statements with Natural Numbers

[trap101]

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

a) 7 | 5²ⁿ + 3 (2^{5n - 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 2^{5n - 2}. Since I'm in the Natural numbers, fractions do not exist, so how do I treat 2^{5n - 2} when n = 0 ?

 

[tiny-tim]

hi trap101!

For n in N (Natural Numbers) …

a) 7 | 5²ⁿ + 3 (2^{5n - 2})
…
Since I'm in the Natural numbers, fractions do not exist, so how do I treat 2^{5n - 2} when n = 0 ?

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

 

[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?

 

[alanlu]

7 is a prime number, so Z₇ 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.

 

[trap101]

ok thanks

 

[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?

 

[alanlu]

You can just prove it...? A mod table is useful for determining values and looking at the overall structure of a Z_n ring, but is not strictly necessary.

Also, consider this for 2 and 5: http://en.wikipedia.org/wiki/Multiplicative_order

 

[Deveno]

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

a) 7 | 5²ⁿ + 3 (2^{5n - 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 2^{5n - 2}. Since I'm in the Natural numbers, fractions do not exist, so how do I treat 2^{5n - 2} when n = 0 ?

you shouldn't have to use a table.

5²ⁿ = (5²)ⁿ, whether mod 7 or not.

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

5²ⁿ = 4ⁿ (mod 7).

now 3(2^5n-2) = 3(2⁵)ⁿ(2^-2).

reduce everything on the right you can mod 7,

you will have (3)(somethingⁿ)(4²) (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.

 

[trap101]

you shouldn't have to use a table.

5²ⁿ = (5²)ⁿ, whether mod 7 or not.

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

5²ⁿ = 4ⁿ (mod 7).

now 3(2^5n-2) = 3(2⁵)ⁿ(2^-2).

reduce everything on the right you can mod 7,

you will have (3)(somethingⁿ)(4²) (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.

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)(4ⁿ 4² (mod 7).

I made bold the 4² 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 4ⁿ(1 + 19)...should that have been 4ⁿ(1+20), to get 21 and thus proving divisibility by 7?

 

[Deveno]

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)(4ⁿ 4² (mod 7).

I made bold the 4² 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 4ⁿ(1 + 19)...should that have been 4ⁿ(1+20), to get 21 and thus proving divisibility by 7?

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)² = 4² (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)(4²) (mod 7)?