All Questions

This question is inspired by the recent answer, where @RobPratt proposed to use integer linear programming (ILP) for solving a number-theoretic optimization problem. I will consider a very similar ...

Modular inverse is known to be computable by Extended Euclidean algorithm which is the reaping the rewards of computing the GCD of two numbers or proving two numbers are coprime. If we already know ...

There are many analogies between the objects $\mathbb F_q[x]$ and $\mathbb Z$. Supposing there is a fixed (say $10^9$) dimension linear integer program (describable without any objective function) in ...

Given $a,b\in\mathbb N$ find $\operatorname{GCD}(a,b)$. Given $a,b,c\in\mathbb N$ find $x,y\in\mathbb Z$ such that $ax+by=c$. Euclidean algorithm solves both. My question is if either 1 or 2 is in ...

Given two primes $p,q\in[T,2T]$, how many integers $m$ of size $O(T^{3/2+\epsilon})$ are there such that the residues $m\bmod p$ and $m\bmod q$ are both $O(polylog(T))$? Looking for an answer Is it ...

I need to emulate this sequence for a program: http://oeis.org/A025302 Stuff that I've taken into account: After finding the prime divisors of a number. I take any divisor as p and apply the ...