Untitled

# Project 1 – Division Algorithm Table (Sec 2.3 style) and Linear Combination
# Fill in your names here (exactly as on Canvas)
group_names <- c("REPLACE WITH YOUR NAMES")

# This script builds the exact 7-column table:
# u1 v1 u2 v2 u3 v3 q
# Start row: 1 0 0 1 a b 0
# Update rules each step (as in notes):
#   q_new  = floor(u3 / v3)
#   u1_new = v1
#   v1_new = u1 - q_new * v1
#   u2_new = v2
#   v2_new = u2 - q_new * v2
#   u3_new = v3
#   v3_new = u3 - q_new * v3
# Stop when v3 == 0. Then:
#   gcd(a,b) = last u3
#   x = last u1, y = last u2 so that a*x + b*y = gcd(a,b)

division_algorithm_table <- function(a, b) {
  stopifnot(a >= 0, b >= 0, !(a == 0 && b == 0))
  # Initial row as in the notes:
  u1 <- 1L; v1 <- 0L
  u2 <- 0L; v2 <- 1L
  u3 <- as.integer(a); v3 <- as.integer(b)
  q  <- 0L
  
  # Store rows in lists
  rows <- list(c(u1, v1, u2, v2, u3, v3, q))
  
  # Iterate until v3 == 0
  while (v3 != 0L) {
    q_new  <- u3 %/% v3
    u1_new <- v1
    v1_new <- u1 - q_new * v1
    u2_new <- v2
    v2_new <- u2 - q_new * v2
    u3_new <- v3
    v3_new <- u3 - q_new * v3
    
    rows[[length(rows) + 1L]] <- c(u1_new, v1_new, u2_new, v2_new, u3_new, v3_new, q_new)
    
    # Move to next
    u1 <- u1_new; v1 <- v1_new
    u2 <- u2_new; v2 <- v2_new
    u3 <- u3_new; v3 <- v3_new
    q  <- q_new
  }
  
  # Build data.frame
  tab <- as.data.frame(do.call(rbind, rows))
  names(tab) <- c("u1","v1","u2","v2","u3","v3","q")
  
  # gcd and linear combination from the last row
  last <- tab[nrow(tab), ]
  gcd_val <- as.integer(last$u3)
  x <- as.integer(last$u1)
  y <- as.integer(last$u2)
  
  list(table = tab, gcd = gcd_val, x = x, y = y)
}

print_pair <- function(a, b) {
  cat("\n--------------------------------------------------\n")
  cat(sprintf("Pair: a = %d, b = %d\n", a, b))
  res <- division_algorithm_table(a, b)
  
  # Pretty print table
  print(res$table, row.names = FALSE, right = TRUE)
  
  # Verify linear combination
  check_val <- a * res$x + b * res$y
  cat(sprintf("\nGCD(a, b) = %d\n", res$gcd))
  cat(sprintf("x = %d, y = %d  ->  %d*(%d) + %d*(%d) = %d\n",
              res$x, res$y, a, res$x, b, res$y, check_val))
  invisible(res)
}

cat("Table columns: u1 v1 u2 v2 u3 v3 q   (last row gives gcd and coefficients x=u1, y=u2)\n\n")

pairs <- list(
  c(512224, 92128),
  c(2084256, 890592),
  c(17601969, 2364768)
)

results <- lapply(pairs, function(p) print_pair(p[1], p[2]))