The best design for finding multiples of 3 and of 5!

[Daniel Keys]

Dear all,

I'm solving the following exercise:

Write a Verilog module for a combinational logic function with one input vector N[5:0] representing an integer between 0 and 63, and two ouputs M3 and M5 indicating wether the integer is a multiple of 3 or 5, respectively.

I could only come up with the following design:

module top_level(N, M3, M5);
	input [5:0]	N	;
	output reg M3, M5	;

	always @ (N)
		begin
			case (N)
				6'd3, 6'd6, 6'd9, 6'd12, 6'd15, 
				6'd18, 6'd21, 6'd24, 6'd27, 6'd30, 
				6'd33, 6'd36, 6'd39, 6'd42, 6'd45, 
				6'd48, 6'd51, 6'd54, 6'd57, 6'd60, 6'd63	:	M3 = 1'd1	;
				default	:	M3 = 1'd0;
			endcase
		end
	
	always @ (N)
		begin
			case (N)
				6'd5, 6'd10, 6'd15, 6'd20, 6'd25, 6'd30, 6'd35, 6'd40, 6'd45, 6'd50, 6'd55, 6'd60	: M5 = 1'd1	;
				default	:	M5 = 1'd0;
			endcase
		end
				
endmodule

However, I find this design very expensive. I am guessing that the synthesizer will generate 21 + 12 = 33 comparators for all the possible matches of the always blocks, with the outputs connectec to two 21-OR and 12-OR ports.

Is there a clever way of detecting multiples of 3 and 5?

All the best,