Modular Arithmetic Word Problems

[Benny]

Hi, I'm currently trying to do some modular arithmetic questions but I don't really know where to start, I don't have much in the way of examples, only a list of theorems. I'm no genius so theorem's by themselves are not enough to enable me to apply them so I've been stuck on some questions. Can someone help me with them?

Q1. Find an $$r \in Z$$ such that $$0 \le r < 713$$ and $$48^{307} \equiv r\left( {\bmod 713} \right)$$. A possible answer is 12.

The next question is similar I think but I haven't been able to figure out what to do.

Q2. Find an m where 0 <= m < n and $$m \equiv l\left( {\bmod n} \right)$$ with l = 482 and n = 14.

I don't necessarily expect anyone to do the whole pronblem for me, even an indication as to the required technique would be good. This is because I really have no idea as to how to approach the first two.

I just have one more question that I would like someone to respond to. I have the following theorem:

Let m and n be in the set of integers Z with m,n > 1. Then, $$\mathop n\limits^\_ \in Z$$ has a multiplicative inverse if and only if gcd(m,n) = 1.

Note: The second sentence has n bar, it's probably a little hard to see. The first sentence in the theorem has n just being n, not n bar.

The following question is from my question booklet and I'm wondering if the theorem applies to it in some way. My understanding of n bar is that it is the set of integers z such that $$z \equiv n\left( {\bmod m} \right)$$. But when I say 'my understanding' I only mean that I know the definition. I'm not really sure at all as to what this means in practice, I'm lacking in suitable examples to work with so any help with the questions would be really good thanks.

Q. Find an inverse for 41 modulo 660, and use it to find the least positive integer x satisfying: $$41x \equiv 125\left( {\bmod 660} \right)$$

Edit: Just one more thing. I have that z_m(z subscript m) denotes the set of all congruence classes modulo m. Does that mean if for example m = 3 then z_m would denote $$\mathop a\limits^\_ = \left\{ {z \in Z|z \equiv a\left( {\bmod 3} \right)} \right\}$$ or something like that?

 

[Benny]

Ok I've sorted out a few things now so I'll restate my question.

Q. Find an integer r such that 0 <= m < 713 such that $$48^{307} \equiv r\left( {\bmod 713} \right)$$.

I don't have problems with questions which ask you to find the LHS. For example find a possible m if $$m \equiv 482\left( {\bmod 14} \right)$$. However doing the reverse is really giving me probems. Now obviously 48^307 is too large a number for me to just evaluate and repeatedly divide by 713. Is there another way which will enable me to find a possible r?

I thought about rewriting 48^307 as factors, some of which are such that $$factor \equiv 1\left( {\bmod 713} \right)$$ so that I can simplify the congruence equation. I've also tried expressing 713 in the for bq + r but that hasn't gotten me very fair either. Can someone please help me out?

 

[shmoe]

For finding high exponents you can use repeated squaring. Find $$48^2, (48^2)^2=48^4, (48^4)^2=48^8,...$$ all mod 713. Then multiply together the appropriate ones to get 307 in the exponent (think of writing 307 in binary). The numbers won't be high as you reduce mod 713 after each squaring.

For finding an inverse of 41 mod 660, you'd like an integer y where $$41y\equiv 1\left( {\bmod\ 660} \right)$$. This just means 660 divides $$41y-1$$, so we have another integer z where $$660z=41y-1$$, or $$660z-41y=1$$. Use Euclid's algorithm, it provides a way of writing the gcd of two numbers as a linear combination of those two numbers (in this case gcd(41,660)=1). If you haven't seen this, examples should be easy to find online, or I can provide one if you ask. Use it just like you'd use a normal multiplicative inverse for solving equations.

It looks like you've sorted out the definition of the little bar. If you have any more questions on the notation, theorems, or whatever, please ask.

 

[Benny]

Thanks for the help.