I paid tax on my first paycheck in the UK. However, I am a resident and am from an EEA country, so the personal allowance should apply to me, but I paid 100 pounds of my 545 pound pay in tax.
Is there any way to rectify that?
You haven't given enough information to identify the reason for tax being withheld, but there are a few possibilities:
Depending on the period of pay covered, you might correctly owe income tax on it. Income tax in the UK is withheld directly from paychecks on the assumption that you will keep getting paid the same amount for the rest of the tax year. For historical reasons, the tax year runs from April 6th to April 5th of the next year, and pay is usually taxed based on when it is received rather than when it is earned.
If for some reason your employer thinks this is a second job, you might not get allocated the personal allowance at all. You should check the "tax code" on your payslip. It should be "1150L" without any other letters/numbers after it. If not, then either your circumstances are actually more complicated, or something is wrong. You should make sure your employer knows this is your only job and your first job in the UK this tax year, and if that doesn't help you should contact HMRC. There's more information on this here.
If your tax code needs to be fixed, normally once this happens your income tax will return to the correct levels and any overpaid tax will be automatically returned through future payslips - you'll see a cumulative amount of income and tax paid on each payslip, and your latest tax code is used to keep the two correctly aligned.
If this doesn't work out and you do end up overpaying tax because the withholding is wrong, you can reclaim it from HMRC. You can either do it after the end of the tax year (i.e. April 2018) once your total income for the year is clear, or under certain circumstances you can ask for a refund immediately. See here for more details.
You are also liable to "National Insurance", a separate tax nominally linked to social security. The threshold for this is lower, and it is actually calculated weekly or monthly rather than over the course of a year - so no refunds later. The threshold for paying it at 12% is £157 per week or £680 per month.
The thresholds for tax and NI are listed here.
If you didn't provide a P60 (income and tax statement from your previous employer) you will be put on emergency tax by your employer's payroll provider. That is, they have no idea what your previous tax position is, what your personal allowance is, how much National Insurance you've paid and will tax it assuming just about the worst possible (from your point) numbers... minimal personal allowance, so the first chunk taxed at 20% and National Insurance taken off it all.
Once they get the correct numbers from the Inland Revenue they will adjust the tax correctly and automatically refund you the overpaid tax.
This happens if you don't provide a P60 / can't provide a P60. It may take 2-3 months for the tax authorities to get the right numbers to your employer's payroll.