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.(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Modular arithmetic + some other stuff on numbers

**Physics Forums | Science Articles, Homework Help, Discussion**