def gcd(a, b)
  b == 0 ? a : gcd(b, a % b)
end

def is_relatively_prime?(a, b)
  gcd(a, b) == 1
end

def multiplicative_order_of_ten(n)
  return nil unless is_relatively_prime?(10, n)
  (2..n-1).each do |i|
    return i if 10**i % n == 1
  end
  return nil
end

def longest_repeating_decimal
  highest_order = 0
  highest_order_n = 0
  (1..1000).each do |n|
    order = multiplicative_order_of_ten(n)
    next if order.nil?
    if highest_order < order
      highest_order = order
      highest_order_n = n
    end
  end
  highest_order_n
end