Try to modify your Makefile for -lgmp rather than -libgmp
In background the compiler adds the 'lib' onto the name as well as the extension .so and similar stuff.
Try running the following to get an overview of what the linker is trying to do:
ld -L [yourincludepath] -lgmp --verbose
Such resolution issues might be due to the fact you are trying to link a 64bit library with a 32bit application? Try installing a proper XX-bits of the lib maybe?
Try to add -m option (machine dependency):
ld -melf_i386 -L /usr/lib/i386-linux-gnu/ -lgmp --verbose
Other values which might be supported on your side:
elf_x86_64 elf32_x86_64 elf_i386 elf_iamcu i386linux elf_l1om elf_k1om i386pep i386pe
More info:
usr/bin/ld: cannot find -l<nameOfTheLibrary>