Summary: The problem of constructing right coprime factorizations (which are based on the graph of an input-output map instead of the Bezout identity) of nonlinear input-output maps is considered. The nonlinear input-output map is assumed to arise from a state variable realization with a fixed initial state. The main result of the paper is that the existence of a stabilizing state feedback implies the existence of a right coprime factorization for the input-output map. The technique is illustrated by application to 1) nonlinear systems which are affine in the control and have a controllable linear part and 2) nonlinear systems which are feedback linearizable. A notion of input-output stability is introduced that requies a bound on the magnitude of the input signals. Methods to construct such bounds are developed as part of the theory and rely on constrained minimization and linear programming techniques for the systems with controllable linear parts. For a locally feedback linearizable system, the problem of input bounds is transferred to the equivalent linear system, while respecting the size of the open set on which the linearizing transformation is valid. This leads to a technique that allows us to map state and input constraints for a feedback linearizable system to the equivalent linear system.