What Are the Fundamental Rules and Procedures of Modular Arithmetic?

[Helicobacter]

I looked at a few modular arithmetic websites and I'm a neophyte when it comes to the legal operations/rules, syntax, and procedures of modular arithmetic. No GRE guide I've seen talks about modular arithmetic (not even the official one!).

Following are five relevant questions from my GRE coaching website (which only gives answers with no explanation).

Trial-and-error is always an option but I'm looking for a systematic approach, clear, efficient step-by-step procedure, which gives me confidence to tackle such problems.
How do I set up the congruent modulo expression?
What operations are allowed in that expression, and which one's are usually performed to reach answers to the below questions with this approach?

x and y are positive integers, where x is a multiple of 3 and x*y is a multiple of 13. The remainder of y/9 is R.
Col A: R
Col B: 1

R is the remainder of (10^32 + 2)/11.
Col A: R
Col B: 3

3 + 3^2 + 3^3 + ……… + 3^x. What is the first value of x at which the sum will be divisible by 6?
A. 15
B. 19
C. 21
D. 28
E. 53

5 is the remainder of x/6 and 3 is the remainder of x/5.
Col A: The least possible value of x
Col B: 23

If y = -(x-1), then what is the value of 1/3(mod(y+x))?

x a positive integer and y is an odd positive integer
Find the remainder when (x+1)*(y+2) is divided by 7

Positive integer Z_1 divided by 7 gives a remainder of 5 and Z_2 divided by 4 leaves a remainder of 3. Some constraint on Z_1 and Z_2 (e.g., they are equal and should be minimum [e.g., Z_1 = Z_2, min(Z_1)], or Z_2 is a defined in terms of Z_1 [e.g., Z_2 = Z_1 +2]).

 

[xaos]

number theory. study it every day for a year and it still won't be enough for the GRE.
1. ? too many variables.
2. 10=-1 mod 11, 100=-1 mod 11...etc
3. 3+3^2=12 =0 mod 6. error.
4. set them equal. inspection.
5. 1/3 mod (1) = ?
6. by inspection. start with small numbers.
7. i didn't read.

notes:
I. for all x>y integrers there exist M,R<y such that x=y*M +R
II. for R=0 ,y divides x or x is a multiple of y; R>0, y divides x-R
III. x = R mod y is the same as y divides x-R which is the same as x=y*M+R

 

[icantadd]

I'm looking for a systematic approach, clear, efficient step-by-step procedure, which gives me confidence to tackle such problems./QUOTE]

The best solution in a case like this is probably a two-fold "program"

Step 0)
Clarify terminology for efficient use and development.
Step 1)
Play around with the ideas behind modular arithmetic .
Step 2)
Gain more formal theory behind modular arithmetic.

Step 0) is a necessary and important step that many people forget about when approaching mathematics through self study. For example, use and internalize terms like mod 17, and Z (the integers) mod 19. Know what your operations are.

Step 1) Most importantly have fun! This is the secret to good math.
Pick some number n and work in Z mod n. In fact pick two. One prime the other not, and possibly pick one large and the other not.
Now the idea is that n = 0, and everything else wraps around. This is like a n-sided polygon (with labeled vertices) that can only be twisted to the right in space. Note you can add two numbers mod some other number. But you have to define subtraction from addition plus wraparound, i.e., find to subtract by some number, b, find c such that b+c = n = 0 and add by c. This will always work in any mod.
Next you have multiplication, but what about division. Is it always the case that you have division? Find out! Consider that you want to divide by some number, b. You must find a number, c, such that bc=1. You may want to look at whether n is prime.
Take a polynomial with integer coefficients. Reduce all the coefficients mod n. Find a solution mod n. Does it tell you anything about the solution in integers.
Make up your own experiments. Diophantine expressions are really neat. What happens when you add multiples of a number mod some other number. How do inequalities work in modular arithmetic.

Step 2)
Modular arithmetic forms a group under addition and a monoid under multiplication, i.e. a ring.
Prove that multiplication and addition are well defined. That is if a mod n = b mod n and c mod n = d mod n then
a+c mod n = b+d mod n
ac mod n = bd mod n
In mod n, for n not prime, you have zero divisors, i.e. non zero elements whose product is 0.
Mod p, for p a prime, you don't. You have a field under addition and multiplication.
What can you deduce from "Fermat's little theorem?"
A weird result is that mod p, f(a) = a^p is a homomorphism. This means in particular, (a+b)^p = a^p+b^p, which is usually not true, and gives some structure reduction in computation. Prove this. When is this map (called the frobenius endomorphism) a bijection, i.e. when is it invertible uniquely? What does this tell you?