# Chinese remainder theorem and Congruence

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

I think that $x^2\equiv 1(mod 55)$ is equal to:

$x\equiv -+1(mod 5)$

$x\equiv -+1(mod 11)$

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

2.I need to prove that for every M positive integer 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 dont now even how to start. I only have an hint that:

$x=0(mod 4),x=-1(mod 9),x=-2(mod 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. –  Beni Bogosel Dec 7 '12 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. –  André Nicolas Dec 7 '12 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$

-