number theoRY!!!

posted by .

How many integers appear in both of the following arithmetic progressions:
A1: 2, 9, 16,.....2+(1000-1)*7
A2: 3, 12, 21,.....3+(1000-1)*9

Since 2 appears in A1 but not in A2, it does not appear in both of the arithmetic progressions.

  • number theoRY!!! -

    A1_n= 2+(n-1)*7=7n-5
    A2_k= 3+(k-1)*9=9k-6

    Put A1_n=A2_k => so 9k-7n=1 and solve the Diophantine equation for n,k u can see that gcd(9,7)=1 so the solutions you want come from applying the euclidean algorithm and your numbers n,k must be less than or equal to 1000.

  • dio -

    Calculating GCD(9,7) gives:

    7 = 0*9 + 7

    9 = 1*7 + 2

    7 = 3*2 + 1

    2 = 2*1 + 0

    Then applying the Extended Euclidean Algorithm:
    1 = (1 * 7) + (-3 * 2)
    = (-3 * 9) + (4 * 7)
    = (4 * 7) + (-3 * 9)
    A particular solution is:
    x0 = -3
    y0 = 4
    The complete solution is:
    x = -3 + 7n
    y = 4 - 9n

Respond to this Question

First Name
School Subject
Your Answer

Similar Questions

  1. Algebra

    Alan and Bob are playing with numbers. Starting with the number n=1 they take turns performing arithmetic manipulations with n. Alan goes first and always multiplies n by 3. Bob adds 1 or 2 to the number n, depending on a coin toss. …
  2. Algebra

    Alan and Bob are playing with numbers. Starting with the number n=1 they take turns performing arithmetic manipulations with n. Alan goes first and always multiplies n by 3. Bob adds 1 or 2 to the number n, depending on a coin toss. …
  3. arithmetic

    Alan and Bob are playing with numbers. Starting with the number n=1 they take turns performing arithmetic manipulations with n. Alan goes first and always multiplies n by 3. Bob adds 1 or 2 to the number n, depending on a coin toss. …
  4. Algebra

    Alan and Bob are playing with numbers. Starting with the number n=1 they take turns performing arithmetic manipulations with n. Alan goes first and always multiplies n by 3. Bob adds 1 or 2 to the number n, depending on a coin toss. …
  5. math

    Alan and Bob are playing with numbers. Starting with the number n=1 they take turns performing arithmetic manipulations with n. Alan goes first and always multiplies n by 3. Bob adds 1 or 2 to the number n, depending on a coin toss. …
  6. maths

    How many integers appear in both of the following arithmetic progressions: A1:2,9,16,……,2+(1000−1)×7 A2:3,12,…,21,…,3+(1000−1)×9 Details and assumptions Since 2 appears in A1 but not in A2, it does not appear …
  7. math

    the integers from 1 to 1000 are printed on a list. how many times does the digit 8 appear?
  8. math!!

    Three numbers are in an arithmetic progression; three other numbers are in a ge- ometric progression. Adding the corresponding terms of these two progressions yields 32, 26, and 32. The sum of the three terms of the arithmetic progression …
  9. number theory

    If you wrote down at all whole numbers from 1 to 1000... 1,2,3,4,5....999,1000 ...which digit would appear the least?
  10. math

    How many terms of the arithmetic sequence 88, 85, 82, . . . appear before the number -17 appears?

More Similar Questions