How to completely remove app from iOS?

There is an app called X in my iPhone which can tell you whether or not you have installed other apps before in this iPhone.

Then I installed an app A into my iPhone, and app X tells me A has not been installed before.

Then I uninstalled app A and then reinstalled it, and app X tells me A has been installed before.

How does X know that A has been installed or not?

And how can I completely remove app A and let app X tells me A has not been installed?

I have jailbreaked my iPhone, is there any app can do that?