# modulo question

• Feb 3rd 2011, 05:54 AM
chrisc
modulo question
Find a number such that 0<x<111 and
(102^70 + 1)^35 = x(mod111)

Any help or tips are much appreciated.

Note for moderator: I originally posted this is the Number Theory forum by accident. I had multiple windows open ready a number of threads. And When I started a new thread, I posted in Number Theory instead of Abstract Algebra where I intended to.
I realized this before a mod messaged me. I was also told my message was moved, but after a few hours I can still see the message in the wrong forum, and now here in Abstract Algebra. If it is in this forum, I cannot see it and you can delete the double. Thank you.
• Feb 3rd 2011, 06:25 AM
roninpro
This can also be considered to be a number theory problem.

It would be nice to use Fermat's Little Theorem / Euler's Theorem, but $\gcd(102,111)=3$. In this case, you can use the Chinese Remainder Theorem - look at the number modulo 3 and 37 and then combine your results to get a common solution modulo 111.
• Feb 3rd 2011, 06:50 AM
CaptainBlack
Quote:

Originally Posted by chrisc
Note for moderator: I originally posted this is the Number Theory forum by accident. I had multiple windows open ready a number of threads. And When I started a new thread, I posted in Number Theory instead of Abstract Algebra where I intended to.
I realized this before a mod messaged me. I was also told my message was moved, but after a few hours I can still see the message in the wrong forum, and now here in Abstract Algebra. If it is in this forum, I cannot see it and you can delete the double. Thank you.

Number theory it is.

CB
• Feb 3rd 2011, 08:15 AM
chrisc
thanks for the tip. I'll work on it after lunch and post an update :)
• Feb 3rd 2011, 01:04 PM
chrisc
Hi again. So I am fairly new to the Chinese Remainder theorem. All my experiences with examples from text and class involve equations where the left side of the mod equation needs to be found.
n = amodb, find n.
Now I need to find a in this question.
I understand the idea of splitting the equation. That is simple. But what change do I need to make from my normal approach?
Would I still go about something like this:

3x + a = (102&70 + 1)^35
so
3x + a = amod37
Just doesn't seem right at this point.

Any further assistance is appreciated.