/sci/ - Science & Math

Oh dear. I meant:

I need a method to find the lowest positive integer r, such that <span class="math">10^r \equiv 1[/spoiler] (mod p), where p is a given prime.

Disguised bump:

Finding r is equivalent to finding the length of the first repunit divisible by p. But that only seems to complicate things.

Why the hell would you ever need that for 26? Do you know long division?

>>5091451
I like trying to do them more mathematically, I learn more.

>>5091451
Also, you couldn't definitely say when the decimal expansion starts repeating.

>>5091416
I'm pretty sure a recursive program is fast enough

>>5091474
I have to do this for all primes less than 1000.

But on examining my program, the speed might not be the problem, but the fact that Visual Basic can't handle numbers above 10^19, and r ends up higher than 19 for a lot of the primes.

So, a method of computing 10^r (mod p), without computing 10^r, would also be incredibly useful.

Assuming p > 10, then 10^(p-1) = 1 mod p, by fermat's little theorem. By lagranges theorem, we have that r divides p-1.

So, for example, if p = 1657, then you only need test the divisors of 1656. Try them starting with the smallest divisors.

>>5091498
10^r (mod p) = 10 (mod p) * 10^(r-1) (mod p)

Basically, you don't need to do every single power before applying the modulus. You can mod by p at every step.

>>5091455
You learn more, but what? Asking 4chan for the answer? Terrible.

Z/pZ is a group under multiplication, and it has p elements.
Lagrange tells us that, if there is a subgroup in Z/pZ, then its size must be a divisor of p.
But p is a prime, so its only divisors are 1 and p.
<10> generates a group, in the form of 10^n, so its size must be either 1 or p.
From that we can get that 10 ^ (size) is 1.
It can't be that size = 1, or else 10^1 = 1, which it doesn't make sense.
So it must be that 10^p = 1.
Thus, the number you're looking for is p.

Note that this doesn't work for p = 2 or p = 5, as 10 mod p = 0, and 0 ^ anything will never produce 1.

>>5091521
Wrong. Z/pZ under multiplication has p-1 elements, not p elements.

>>5091498
>>5091509
Thank you, this seems very helpful. Modular arithmetic is lovely.

>>5091524
I'm not asking for the answer, I'm asking for a possible way forward, and somebody has helped, and I now know more than I did before.

Here's what I started studying this month.

Hurray, I got the answer.

>10^r (mod p) = 10 (mod p) * 10^(r-1) (mod p)

Was what helped.

Time to laugh at other people's brute force algorithms in the forum.