we must use the instrumental case
Yes.
which ends in -ой for fem. and -ом for masc.
Unfortunately, it's not always so simple.
The ultimate Russian noun-endings list