#| BEGIN (Write your solution here) |#
(define (square n)
  (* n n))

(define (remainder-check x m)
  (if (and
        (not (= 1 x))
        (not (= (- m 1) x))
        (= (remainder (square x) m) 1))
      0
      (remainder (square x) m)))

(define (expmod-check base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder-check (expmod-check base (/ exp 2) m) m))
        (else
         (remainder 
          (* base (expmod-check base (- exp 1) m))
          m))))

(define (miller-rabin-test n)
  (define (try-it a)
    (= (expmod-check a (- n 1) n) 1))
  (try-it (+ 1 (random (- n 1)))))
#| END |#