sahasumit288's blog

Arithmetic Progression and modulo cycle
By sahasumit288, history, 8 years ago, In English

Suppose I have an arithmetic sequence.

a+ (a+d) +a(a+2d)......

Here d is greater thanzero. I want mod this arithmetic sequence with M.

(a)%M + (a+d)%M + (a+2d)%M +(a+3d)%M................ Now I want to know, Any cycle will be created? If create when and why? How can I figureout the cycle?

Sorry for my bad english.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

when coefficient of d equals M from then a cycle will be created. cause (a+Md)%M =(a%M + Md%M)%M =(a%M+0)%M =(a%M)%M =a%M which is equal 1st term. I apologize if I couldn't understand what you meant or if you dislike my answer.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

a+(a+d) +a(a+2d) -- is arithmetic sequence ????

If you suppose 

a[0] = a, a[1] = a + d, a[2] = a + 2d, ..., a[i] = a + i*d

arithmetic sequence, so for any i , 

 a[i] % M = a[i%M] % M.

proof: let p = i div M, q = i mod M, ==> i = p*M + q

a[p*M+q] % M = (a + (p*M+q) * d ) % M =  ( a + (p*M+q)%M * d)%M = (a + q *d ) % M = a[q] % M = a[i%M]%M.

so cycle will be created at most next M step, for another cases check divisors of M(but, I am not sure).

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

Suppose two terms (a + bd and a + cd) have the same value mod M. Then, their difference must be a multiple of M. So, (c — b) * d has to be a multiple of M. Since we want the smallest cycle, we want to minimize (c — b), which is the same as minimizing M since d is a constant. This is exactly the problem of the LCM (least common multiple) of M and d, which can be found using the Euclidean algorithm for GCD. Then, the cycle length is just LCM(M, d) / d terms and starts at the first term.

→ Reply