How to prevent users from changing their password to one of the last X passwords?

I have an Ubuntu GNOME 15.10 with GNOME 3.18 system which I would like to set up so that the users using it cannot set a new password as one of the previous X passwords, how can this be achieved?

When I change my password, if it is too similar to my last my system does not allow me to change it to that password, it would be good if the answer could also show how to extend this so that the new password can also not be too similar to the previous X recorded passwords.

Note: The history of the last X passwords should not be stored in an insecure unencrypted manner, in fact they should probably be stored in the same or similar way to the way in which the current password is stored (as a salted hash).

I have used X to represent the number of passwords (this could be any value) because I want to be able to easily change the amount of passwords stored which cannot be used, and also so that others can easily take the answer and use it as they wish rather than having an answer which revolves around a very set value for X.

Information Update:

As requested here is the contents of my (excluding the comments at the top) /etc/pam.d/common-password file:

# here are the per-package modules (the "Primary" block)
password        [success=1 default=ignore]      pam_unix.so obscure sha512
# here's the fallback if no module succeeds
password        requisite                       pam_deny.so
# prime the stack with a positive return value if there isn't one already;
# this avoids us returning an error just because nothing sets a success code
# since the modules above will each just jump around
password        required                        pam_permit.so
# and here are more per-package modules (the "Additional" block)
password        optional        pam_gnome_keyring.so
# end of pam-auth-update config

You can configure PAM to do this for you. Just open /etc/pam.d/common-password and append use_authtok to the first password line (the one which calls the pam_unix module) so that it looks somewhat like this:

password    [success=1 default=ignore]  pam_unix.so obscure sha512 use_authtok

Now add this line above the previously modified line:

password    required    pam_pwhistory.so  remember=X

where X is the number of previous passwords against which you want to check for a repeating password.

Here the previous X passwords will be stored in hashed form at the location /etc/security/opasswd

So you need to create the file if and only if it does not exist and assign it permission 600 (-rw-------):

sudo touch /etc/security/opasswd
sudo chmod 600 /etc/security/opasswd