Can you go into Image > Image Size, and give us the original dimensions in pixels and the resolution in ppi?
It would also help to know the version of Photoshop and what OS you are using.
Any time you interpolate an image you will lose some image quality. You either throwing away detail you have or creating detail you don't have. Increasing the number pixel may help you print a larger acceptable image however interpolation can do just so much.
That's true, but there may be a way out. The print resolution.
If it is high enough, we can try "scaling".
a 4 x 5 image @ 300 ppi and be printed on an 8 x 10 at 150 ppi with no resampling penalties.
Uncheck "resample" in the Image size dialog, and see if it can be changed to a larger size by inputting the A4 size.
The resolution can be dropped down and might not be noticed on a sheet of A4 paper (something like our 8 1/2 x 11)
It will work if the resolution is 300, may not work if it is 72, unless the inches are way larger at that size.
Thanks for getting back to me.
Without sounding silly, could you possibly dumb it down for me, I'm a first time user to Photoshop.
However, I am using the Photoshop CC 2014 on Windows 7.
Let's see. Here is a simple way:
Open your image
Go to File > Print...
Under Position and Size
Check mark Scale to Fit Media and print it out on your A4 paper.
Does it look good to you?
What you did was known as "scaling". If there are enough pixels, you can change the print size with noticing anything wrong.
That's the best, because you are not adding or subtracting pixels, which is called "re-sampling".
If the scaling did not work then you would use Image Size to enlarge the picture by guessing what pixels to add. Not the best way to go, because you are adding information not in the picture to make it look better.
My Advice: If you have a camera, use the highest MP setting, shoot jpeg best quality, or even better RAW
If you scan, plan. 300 ppi is a good start and should give you plenty of pixels at A4.
That really the simple story. Read up to understand digital images.