какой частью речи является слово не должен

Здесь два слова, следовательно, две части речи.

НЕ – отрицательная частица.

ДОЛЖНЕН, согласно школьной частеречной классификации, – это КРАТКОЕ ПРИЛАГАТЕЛЬНОЕ, которое в современном русском языке не имеет полных форм. И, на мой взгляд, именно это верно.

ДОЛЖЕН – это краткое прилагательное, так как:
● на вопрос КАКОВ? отвечает;
● ИЗМЕНЯЕТСЯ по числам (должен – должны), а в единственном числе по родам (должен – должна, должно);
● в предложении может быть сказуемым (Я ему должен) или вспомогательной частью с нулевой или выраженной связкой составного глагольного сказуемого (Чем я должен руководствоваться? Чем я должен был (буду) руководствоваться?).

Когда-то прилагательное ДОЛЖЕН имело полную форму ДОЛЖНЫЙ, но так как полное прилагательное давно утратило значения «имеющий какой-либо долг, обязанность, денежное или иное обязательство», «взятый в долг; не отданный – о деньгах)» и стало употребляться в значениях «такой, как нужно; подобающий, соответствующий», «такой, каким следует, подобает быть», то оно утратило свои краткие формы, которые «стали жить» самостоятельно, сохранив утраченные полными формами значения.

Определение слова ДОЛЖЕН как наречия в функции сказуемого, то есть слова категории состояния, данное в словаре Кузнецова, не выдерживает критики, так как слово ДОЛЖЕН изменяемое (см. в моём ответе выше), а слова категории состояния, как и наречия, не изменяются.