Ну как бы это фундаментальная теорема о том, что все числа состоят из уникального набора простых множителей. А то, что вы наблюдаете - это ее следствие. Т.е. два разных взаимно-простых числа больших двойки по определению нельзя разделить друг на друга так, чтобы получилось целое число...
Я бы пошел от обратного: брал бы какое-то число и уможал его на два случайно выбранных числа, в таком случае изначально выбранное число и было бы ответом. Т.е.

Код AS3:
var x:int = Math.sqrt(Math.random() * int.MAX_VALUE);
var multiplierA:int = Math.sqrt(Math.random() * int.MAX_VALUE);
var multiplierB:int = Math.sqrt(Math.random() * int.MAX_VALUE);
return [x * multiplierA, x * multiplierB];
EDIT:
Ой, я думал речь идет о нахождении числа, которое делит два других.
Ну так а если просто нужно найти любые X, Y, такие чтобы X / Y - целое, то достаточно:

Код AS3:
var maxMultiplier:int = Math.sqrt(int.MAX_VALUE);
var x:int = Math.random() * maxMultiplier;
var y:int = Math.random() * maxMultiplier;
return [x * y, y, x];