Modular arithmetic + some other stuff on numbers

[Benny]

Hi, I've just begun studying modular arithmetic and as yet, I haven't got a reference text to work from so I'm hoping that someone can help me out with the following questions.

Q. Calculate 7^2(mod 13), 7^4(mod 13), 7^8(mod 13) and 7^9(mod 13).

I can't think of a way to do this without actually working out 7^n and repeatedly subtracting multiples of 13. Is there a pattern to this? The answers are:

<br /> 7^2 \equiv 10\left( {\bmod 13} \right),7^4 = 9\left( {\bmod 13} \right),7^8 \equiv 3\left( {\bmod 13} \right),7^9 \equiv 8\left( {\bmod 13} \right)<br />.

So for the first one with 7^2 identically equal to 10(mod13) that just means that the difference between 7^2 and 10 is exactly divisible by 13 right? It turns out that 7^2 - 10 = 39 which is exactly divisible by 13. The 'remainder' is 10. I'm wondering if there is a standard procedure to evaluate the expressions in the question or if brute force is required.

I just have some other really basic questions which I would like some help with. I have no confidence when dealing with anything even vaguely related to number theory so I'd really like some help with these.

Q. Suppose a divides b. Show that a^m divides b^m for all integers m > 0.

So by definition of b I have b = ca for some integer c. b^m = (ca)^m = (c^m)(a^m). I have that c is an integer so that c^m is also an integer since m is a positive integer. If I set d = c^m then I get b^m = da^m so that a^m divides b^m. I just seem to be stating the obvious so I'm not sure about this one.

Q. Suppose that a divides al the integers x_1, x_2,...,x_n. Show that a divides the linear combination: \lambda _1 x_1 + ... + \lambda _n x_n where each of the lamdas are integers.

Ok so a divides each of the x_i, i = 1,2...,n. So c_1 a + c_2 a + ... + c_n a = x_1 + x_2 + ... + x_n

<br /> \Rightarrow \left( {\lambda _1 c_1 + \lambda _1 c_2 + ...\lambda _n c_n } \right)a = \lambda _1 x_1 + \lambda _2 x_2 + ...\lambda _n x_n <br />

<br /> \lambda _1 x_1 + \lambda _2 x_2 + ... + \lambda _n x_n <br />

<br /> b = \left( {\lambda _1 c_1 + \lambda _2 c_2 + ...\lambda _n + c_n } \right) \in Z \Rightarrow b \in Z<br />

The result follows from that? Any help would be appreciated.

 

[lurflurf]

Hi, I've just begun studying modular arithmetic and as yet, I haven't got a reference text to work from so I'm hoping that someone can help me out with the following questions.

Q. Calculate 7^2(mod 13), 7^4(mod 13), 7^8(mod 13) and 7^9(mod 13).

I can't think of a way to do this without actually working out 7^n and repeatedly subtracting multiples of 13. Is there a pattern to this? I'm wondering if there is a standard procedure to evaluate the expressions in the question or if brute force is required.

I don't know about standard procedure or tricks as i have not had reason to do complicated modular arithmatic, but it helps to do reductions in intermediate steps. Also powers can be done in terms of powers of two and powers become cyclic
7^0=1
7^1=7
7^2=49=10
7^3=70=5
7^4=35=9
7^5=63=11
7^6=77=12
7^7=84=6
7^8=42=3
7^9=8
7^10=4
7^11=2
7^12=1
7^13=7
7^14=10
and so on
7^n=7^mod(n,12)
power of 2 powers are also nice
7^(2^0)=7^1=7
7^(2^1)=7^2=10
7^(2^2)=10^2=9
7^(2^3)=9^2=3
7^(2^4)=3^3=9
7^(2^5)=9^2=3
and so on with alternating 9 and 3
this makes your problem easy
7^2,7^4,7^8 appear naturally
7^9=(7^1)(7^8)=7*3=8


I just have some other really basic questions which I would like some help with. I have no confidence when dealing with anything even vaguely related to number theory so I'd really like some help with these.

Q. Suppose a divides b. Show that a^m divides b^m for all integers m > 0.

So by definition of b I have b = ca for some integer c. b^m = (ca)^m = (c^m)(a^m). I have that c is an integer so that c^m is also an integer since m is a positive integer. If I set d = c^m then I get b^m = da^m so that a^m divides b^m. I just seem to be stating the obvious so I'm not sure about this one.
Yes it is that obvious
Q. Suppose that a divides al the integers x_1, x_2,...,x_n. Show that a divides the linear combination: \lambda _1 x_1 + ... + \lambda _n x_n where each of the lamdas are integers.

Ok so a divides each of the x_i, i = 1,2...,n. So c_1 a + c_2 a + ... + c_n a = x_1 + x_2 + ... + x_n

<br /> \Rightarrow \left( {\lambda _1 c_1 + \lambda _1 c_2 + ...\lambda _n c_n } \right)a = \lambda _1 x_1 + \lambda _2 x_2 + ...\lambda _n x_n <br />

<br /> \lambda _1 x_1 + \lambda _2 x_2 + ... + \lambda _n x_n <br />

<br /> b = \left( {\lambda _1 c_1 + \lambda _2 c_2 + ...\lambda _n + c_n } \right) \in Z \Rightarrow b \in Z<br />

The result follows from that? Any help would be appreciated.[/QUOTE]
For this one it I would show
a|b & a|c -> a|(b+c)
and
a|b -> a|(kb)
then use induction to get the general result
That makes it more clear for me personally
Your approch is right though

 

[Benny]

Thanks for your help lurflurf.

After going through my first post again I see that I made a mistake when I typed out my answer. The bit with b = (...) should have the product lamba sub n and x sub n instead of the sum of those two terms.

 

[matt grime]

wheneever you are doing modular arithmetic you can reduce mod whateever *at any time*. the standard short cut is to raise things to powers of 2 since that is just squaring.

example 7^51 mod 13.

7^2=49=10 mod 13

so this is 7.10^25 mod (13)

and you could repeat this, idea.

the next best is to work out 7^2, then (7^2)^2 =7^4 and ((7^2)^2)^2=7^8
(((7^2)^2)^2)^2)=7^16 and that with 5 raises of the power 2. do this by square and reduce square and reduce each time.

then 51 = 32+16+4+1 so 7^51=7^(32)7^(16)7^(4)7

a better way yet is to nkow fermat's little theorem: if a and p are comprime and p is a rime then a^{p-1}=1 mod p

so 7^12=1 mod 13 hence 7^51 = 7^{48}7^3=7^3 mod 13