- #1

Benny

- 584

- 0

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:

[tex]

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)

[/tex].

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: [tex]\lambda _1 x_1 + ... + \lambda _n x_n [/tex] where each of the lamdas are integers.

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

[tex]

\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

[/tex]

[tex]

\lambda _1 x_1 + \lambda _2 x_2 + ... + \lambda _n x_n

[/tex]

[tex]

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

[/tex]

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

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:

[tex]

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)

[/tex].

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: [tex]\lambda _1 x_1 + ... + \lambda _n x_n [/tex] where each of the lamdas are integers.

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

[tex]

\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

[/tex]

[tex]

\lambda _1 x_1 + \lambda _2 x_2 + ... + \lambda _n x_n

[/tex]

[tex]

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

[/tex]

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

Last edited: