I was reading the book (21 Aulas de matmática Olímpica - C. Shyne), and I came across the following problem:
Find two factorizations of $x^2-4 \pmod4$.
I know this is a simple problem, but I couldn't understand what it means to factor a polynomial modulo $4$. Can anyone help?
further to J.W. Tanners reply,
a polynomial modulo 4 means an integer polynomial where the coefficients are modulo 4,
so eg $7*x^4+9*x^3+1$ is the "same" as $3*x^4+13*x^3+4*x+5$, because the coefficients are the same modulo 4. In particular a polynomial which doesnt factorise as an integer polynomial eg $x^2-5$, could factorise modulo 4, eg $x^2-5$ is the same as $x^2-1$ which factorises as $(x-1)(x+1)$. J.W Tanner has found an alternative factorisation by replacing the polynomial by one which is the "same".
polynomials modulo a prime number are "better behaved" than those modulo a composite number such as 4, because modulo a prime you have "unique factorisation" of polynomials, and you can extend the domain of the function so that all polynomials factorise into linear factors, both all polynomials over the original domain AND all polynomials over the extended domain, this extending is referred to as "algebraic closure", but both these results require some work and would be in an undergraduate pure maths course and could come up as "bookwork" questions in say a 2nd year exam. I am not aware of any nice way of expressing the algebraic closure of the integers modulo a prime, but there are nice ways to extend the integers modulo a prime to factorise a specific polynomial into linear factors. With all these things you have to wade through some theory.
The example JW Tanner gave shows that you dont have unique factorisation modulo 4, but modulo a prime you cannot factorise into "different" ways. By "different" we mean we cannot transform one factor into another by multiplying by an invertible constant or equating coefficients via modulo. eg 1 and 3 are the invertible constants modulo 4, so eg $x-2$ is equivalent to $3x-2$ because $3x-2=3*(x-2)$ modulo 4, and its also equivalent to $3x+2$ by equating coefficients modulo 4. $(x-2)*(x+2)$ is regarded as equivalent to $(3x+2)*(x+6)$ but its not equivalent to $x*x$. Modulo a prime, all factorisations are equivalent, hence the set of polynomials modulo a prime is called a unique factorisation domain or UFD. Rearranging the order of factors is also regarded as equivalent. Essentially its like regarding $6=2*3$ and $6=3*2$ and $6=(-3)*(-2)$ as "equivalent" factorisations of 6 over the integers, where the integers are the archetypal UFD. To generalise the ideas, we regard $-3$ also as a prime over the integers and equivalent to $3$.
These are important concepts, but they are some work to establish properly!
Galois Theory is one subject which focusses on this kind of thing, but you need to learn more basic algebra before trying to study this, typically Galois Theory may be a 2nd or 3rd year course at uni, its definitely too specialised for the first term of the first year, and probably too specialised for the first year. For a book that covers foundations AND Galois Theory, "Algebra" by Thomas W. Hungerford is good, by Springer Verlag. There are books which cover just Galois Theory but you are diving in the deep end if you are teaching yourself. Hungerford's book is a good reference book because it covers diverse topics eg the axiom of choice.
As a student I NEVER worked through Hungerford's book, but I OFTEN used it as a reference to look up technical things I was unsure of eg things glossed over by the courses.