Another boring modular arithmetic question

[Avocado]

Suppose x = b^n mod m, all positive integers.

If b = 3 and m = 10, the only values x can assume are 1, 3, 7 and 9.

If b = 2 and m = 7, the only values x can assume are 1, 2 and 4.

I want to know if there's a way to find out how many values x can assume, given a base b and a module m, without calculating b^n.

ps: sorry for posting these basic / boring questions on this awesome forum, but i don't know where else to ask.

[thylacine]

[ QUOTE ]
Suppose x = b^n mod m, all positive integers.

If b = 3 and m = 10, the only values x can assume are 1, 3, 7 and 9.

If b = 2 and m = 7, the only values x can assume are 1, 2 and 4.

I want to know if there's a way to find out how many values x can assume, given a base b and a module m, without calculating b^n.

ps: sorry for posting these basic / boring questions on this awesome forum, but i don't know where else to ask.

[/ QUOTE ]

I'll let someone else give info, but these are not "basic / boring questions" by any means.

[Wyman]

[ QUOTE ]
Suppose x = b^n mod m, all positive integers.

If b = 3 and m = 10, the only values x can assume are 1, 3, 7 and 9.

If b = 2 and m = 7, the only values x can assume are 1, 2 and 4.

I want to know if there's a way to find out how many values x can assume, given a base b and a module m, without calculating b^n.

ps: sorry for posting these basic / boring questions on this awesome forum, but i don't know where else to ask.

[/ QUOTE ]

We could get mathy here (and talk about the order of the subgroup generated by b in the multiplicative group (Z_m)*, for b relatively prime to m anyways), but the right way to look at this is by example. How can we see that there are only 4 values for 3^n mod 10?

The first thing we should notice is:
(a * b) mod m = [(a mod m)*(b mod m)] mod m
[I'm sorry if this is already clear to you, but I will prove it anyway]

Proof: This is a straightforward application of the division algorithm. Write a = r + jm, b = s + km, where r and s are between 0 and m-1 (inclusive), so that a mod m = r, and b mod m = s.
Now (a*b) mod m = (rs + m (js + kr + jkm)) mod m
= rs mod m
= [(a mod m)*(b mod m)] mod m.

This is great -- let's see why. We can show that there's only 4 values for 3^n mod 10.

Well, 3^1 = 3, 3^2 = 9, 3^3 = 27, 3^4 = 81, 3^5 = 243, ...
It gets cumbersome to compute all of these, though.

3^1 mod 10 = 3
3^2 mod 10 = 9
3^3 mod 10 = 7
We use the fact we proved above to see:
3^4 mod 10 = [(3^3) * 3] mod 10
= (7 * 3) mod 10
= 1
Do you see the easy reason (rather than 3^5 = 243) why 3^5 mod 10 = 3?
[3^5 mod 10 = [(3^4) * 3] mod 10
= (1 * 3) mod 10
= 3 ]

Or why 3^n mod 10 = 3^(n+4) mod 10 for any n?

Let's look at your b=2, m=7 example:
2^1 = 2
2^2 = 4
2^3 = 8, but 8 mod 7 = 1.
[You should see by now that once we get to 1, we're done.]
So x can be 1, 2, or 4.

Ok, so when b and m are relatively prime, the above holds (trust me?). That is, we take successive powers until b^k mod m = 1. What about if b and m are not relatively prime? Let's take 2 and 10.

2, 4, 8, 6, 2, 4, 8, 6, ...

Notice we never got back to 1, but we're repeating anyway. We could prove this if we wanted to, but the fact we proved above should convince you that if you repeat once, you repeat always (DUCY?).

So, you don't need to compute b^n (where n is presumably large) in order to figure out a number of putative values for x. You just need to compute (mod m, of course, so no need for big computations) b, b^2, ..., b^k until you see b appear again in this list.

I hope this answered your question. If you just want to look at b and m and know how many values for x there are, I am stuck for a way.

[Avocado]

Thanks Wyman,
To be honest I was looking for a magical way to know the answer just looking at b and m /images/graemlins/smile.gif, but it seems that it's impossible.
I did know about the repetitions, but even with this "shortcut", the computation takes too much time for big numbers (specially primes).

Thanks again, I'll see what I can do.

[thylacine]

[ QUOTE ]
Thanks Wyman,
To be honest I was looking for a magical way to know the answer just looking at b and m /images/graemlins/smile.gif, but it seems that it's impossible.
I did know about the repetitions, but even with this "shortcut", the computation takes too much time for big numbers (specially primes).

Thanks again, I'll see what I can do.

[/ QUOTE ]

Do you have a factorization of m and \phi(m) ?

Do you know why I asked this ?

Anyway, Wyman's 1st half sentence gets to the point, assuming b is a unit in Z_m .

[bigpooch]

If either b or m is a prime, it may not take THAT much
time on a computer as long as one is efficient about it. If
either b or m is a prime, a key piece of information is the
prime factorization of phi(m). You know that b^k=1 for some
k<=phi(m) from Euler's theorem and the least such k gives
the number of different values of b^n (which is the "order"
of b (mod m)). For example, if m=100, phi(m)=phi(4)*phi(25)
=2*20=40 and so if b is coprime to m (b is not divisible by
either 2 or 5), b must have an order (mod 100) that is a
divisor of 40. Thus, you first need to check for
"exponents" 40/2 and 40/5:

Calculate b^20, b^8 to see if either is 1 (mod 100).

If not, b has order 40. But if b^20 or b^8 is 1 (mod 100),
you make further checks for smaller exponents. Usually, you
have information where it is redundant to make certain
calculations: e.g., if b^20=1 (mod m) but b^8<>1 (mod m),
although 20/5=4 is an exponent you might check, it's
unnecessary since if the order of b were 4 (mod m), b^8=1
(mod m), so you only need to check the exponent 20/2=10 and
then, if necessary, the exponent 5.

In fact, for m=100, since phi(m)=40=(2^3)*(5^1), you only
need to check for (3+1)(1+1)=4x2=8 exponents (actually, this
includes the check to see if b=1 (mod m)) but of course, you
want to execute this check efficiently.

Also, when evluating b^n (mod m), it is useful to simply
have a squaring function (mod m). You store the result for
b (mod m) (all your results can be an integer in (-m/2,m/2]
or [0,m-1] if you prefer). Once you have b^2 (mod m), you
store that result and continue to make the calculations for
(b^2)^2=b^4 (mod m), (b^4)^2=b^8 (mod m), but you don't
need any exponent 2^j>=phi(m) because if x and y are
congruent mod (phi(m)), then b^x = b^y (mod m) [the only
requirement is that b and m are coprime].

Having these values makes it much easier to compute b^n for
arbitrary n in the future since if you have n in binary,
it's just a matter of multiplications by the appropriate
powers of 2^k of b for the "on-bits" for n. And of course,
every result you get is in (mod m), so you only need to
have the result as an integer in (-m/2,m/2] or [0,m-1].

Are there any restrictions at all on b, n and m?