# Chinese remainder theorem and Congruence

1. $$x^2\equiv 1 \pmod {55}$$ I need to find all the solutions {$$0,1,...54$$}.

I think that $$x^2\equiv 1 \pmod {55}$$ is equal to:

$$x\equiv \pm1 \pmod 5$$

$$x\equiv \pm1 \pmod {11}$$

Actually I tried to solve from here by the Chinese remainder theorem but I'm stuck so I guess I'm doing something wrong.

2.I need to prove that for every positive integer $$M$$ there are $$M$$ בonsecutive numbers that each one of them is full square.

For example : 8 divided by $$2^2$$ and 9 by $$3^2$$.

This question I don't know even how to start. I only have an hint that:

$$x=0 \pmod 4 ,x=-1 \pmod 9, x=-2 \pmod {25}$$ and so on...

• One elementary way would be to use that $55 | (x-1)(x+1)$, and work on cases. 1) $55|x-1$ or $55|x+1$ 2) $11|x-1$ and $5|x+1$ etc. Dec 7, 2012 at 23:30
• The hint for 2) is almost a full solution. First it is important to understand what you have been asked to prove. You want to show that there are $M$ consecutive integers each of which is divisible by a square $\gt 1$. Let's do it for $M=4$, but it's all the same. By Chinese Remainder Theorem, there is an $x$ such that $x\equiv 0\pmod{2^2}$, $x\equiv -1\pmod{3^2}$, $x\equiv -2\pmod{5^2}$, $x\equiv -3\pmod{7^2}$. Then $x$ is divisible by $4$, $x+1$ is divisible by $9$, $x+2$ is divisible by $25$, and $x+3$ is divisible by $49$. For your moduli, use squares of the primes. Dec 7, 2012 at 23:48

1) Because $5$ and $11$ are relatively prime, $55$ divides $x^2-1$ iff $5$ divides $x^2-1$ and $11$ divides $x^2-1$. Equivalently, $x^2\equiv 1\pmod{55}$ iff $x^2\equiv 1\pmod{11}$.

The solutions of $x^2\equiv 1\pmod{5}$ are $x\equiv \pm 1\pmod{5}$, because $5$ is an odd prime. Similarly, the solutions of $x^2\equiv 1\pmod{11}$ are $x\equiv \pm 1\pmod{11}$.

So modulo $55$, there are $4$ solutions. They are the solutions to the systems

(i) $x\equiv 1\pmod{5}$, $x\equiv 1\pmod{11}$;

(ii) $x\equiv -1\pmod{5}$, $x\equiv -1\pmod{11}$;

(iii) $x\equiv 1\pmod{5}$, $x\equiv -1\pmod{11}$;

(iv) $x\equiv -1\pmod{5}$, $x\equiv 1\pmod{11}$;

Note that the solutions to (i) and (ii) are obvious, they are $x\equiv 1\pmod{55}$ and $x\equiv -1\pmod{55}$.

Note also that $x$ is a solution of (iii) iff $-x$ is a solution of (iv). So all we need to do is to solve (iii). Then the answer to (iv) will be automatic.

Trotting out the full CRT machinery seems like overkill for such small numbers. By the first congruence, $x=5y+1$ for some $y$. By the second, $11$ divides $x+1$. So $11$ divides $5y+2$. By inspection, $y=4$ works. That gives $x=21$. If we don't quite want to use inspection, write $5y\equiv -2\pmod{11}$. Multiply by $2$. We get $10y\equiv -4\pmod{11}$. But $10\equiv -1\pmod{11}$, so we get $-y\equiv -1\pmod{11}$, that is, $y\equiv 4\pmod{11}$.

2) The problem almost certainly asks you to prove that for any positive integer $M$, there exists a sequence of $M$ consecutive integers such that each integer is the sequence is divisible by some square $\gt 1$.

We will do it for the case $M=5$. We take any $5$ distinct primes, say $2$, $3$, $5$, $7$, and $11$. By the Chinese Remainder heorem, there is an $x$ that satisfies the following system of congruences:

$x\equiv 0\pmod{2^2}$, $x\equiv -1\pmod{3^2}$, $x\equiv -2\pmod{5^2}$, $x\equiv -3\pmod{7^2}$, $x\equiv -4\pmod{11^2}$.

We can also if we wish arrange for $x$ to be positive.

Since $x\equiv 0\pmod{2^2}$, we have that $x$ is divisible by $2^2$. Since $x\equiv -1\pmod{3^2}$, we have that $x+1\equiv 0\pmod{3^2}$, that is, $3^2$ divides $x+1$. A similar argument shows that $x+2$ is divisible by $5^2$, and that $x+3$ is divisible by $7^2$, and that $x+4$ is divisible by $11^2$. Thus each of the $5$ consecutive integers $x,x+1,x+2,x+3,x+4$ is divisible by a perfect square $\gt 1$.

$11+(-2)(5)=1$ Using the Chinese remainder theorem we know that there exists $x$ such that:

1) $5,11|x-1$ This $x$ is $11(1)+(-2)5(1)=+1$

2) $5,11|x+1$ This $x$ is $11(-1)+(-2)5(-1)=-1$

3) $5|x-1$ and $11|x+1$ This $x$ is $11(-1)+(-2)5(1)=-21=34$

4) $5|x+1$ and $11|x-1$ This $x$ is $11(1)+(-2)5(-1)=21$