Army of Mages

Everybody was silent. It became known that after the North battle all warriors of the great Coalition Army would stop defending their kingdom as battle mages and would serve as coaches. So it was the time to build a new powerful army. It was the wise Sandro who broke the silence and began to write down the names of the candidates. Finally, he wrote down $5n$ names. But only $n$ best mages had to be chosen according to the law of the kingdom. After a long discussion it was decided to build an army in such a way that every two mages in this army would respect each other.

All mages in the kingdom live in their own houses, situated at the points on the plane with integer coordinates. Somewhy two mages respect each other if and only if a line segment connecting their houses contains at least one point with integer coordinates, different from endpoints of this segment. For example, if there are houses at points ($1$, $1$) and ($5$, $5$) then their inhabitants respect each other, because there is a point ($2$, $2$) on this segment. In the same time, inhabitants of the houses situated in ($0$, $0$) and ($1$, $10$) don't respect each other. Help the government to build an army!