Waste less time on Facebook — follow Brilliant.

A modulus rule that I found out, can anyone help me prove or disprove this?

For any number \(x\) where \(x>=2\) and any number \(y\) which \(y\) mod \( x \ne 0\)

\( (x+y)^2 \) mod \(x\) is equal to 1

I'm not quite sure how this can be useful, or if people have discovered it, but who knows. Please tell me if people have, and I'm coding a program that'll test it up to about a 100 in x and 1000 in y. I'll be back with the results and the github link to the program.

Note by Zaid Baig
2 years, 2 months ago

No vote yet
1 vote


Sort by:

Top Newest

The statement is false... let me disprove it...

Assume the statement is true, that is for any number \(x\geqslant 2\) and for any number \(y\) and \(x\nmid y\) which is \(y\not\equiv 0 \pmod{x}\). \[\begin{align} \\ (x+y)^2&=x^2+2xy+y^2 \\&\equiv y^2 \\&\equiv 1 \pmod{x} \\ \end{align}\] Hence \(y^2-1\) must be divisable by \(x\), now we can conclude for any number \(y\) and \(x\nmid y\), \(x\mid y^2-1\).

However, since \(y^2-1=(y+1)(y-1)\), by Euclid's lemma, we get either \(x\mid y+1\) is true or \(x\mid y-1\) is true, so the equivalence \((x+y)^2 \equiv 1\pmod{x}\) cannot hold if \(x\mid y+1\) and \(x\mid y-1\) are both false.

For example, assume \(x=5\) and \(y=7\), we have satisfied the conditions \(y\not \equiv 0 \pmod{x}\) and \(x\geqslant2\), here, \(x\mid y+1\) and \(x\mid y-1\) are both false. \[\begin{align} \\ (x+y)^2&=(5+7)^2 \\&=12^2 \\&=144 \\&\equiv 4 \\&\not \equiv 1\pmod{5} \\ \end{align}\]

Other pairs of counterexamples \(\{x,y\}\) are \(\{10,8\}\), \(\{6,13\}\), \(\{25,9\}\)... (there are infinity of them!) This statement can be made true if you add one more condition: one of the numbers \(y+1\) or \(y-1\) must be divisable by \(x\).

Therefore, the corrected statement are as follows:

For any number \(x\geqslant2\), \(y\), \(x\nmid y\), if either \(x\mid y+1\) or \(x\mid y-1\) is true, then \[(x+y)^2\equiv 1 \pmod{x}\]

For example, assume \(x=6\), \(y=5\), we have satisfied \(x\geqslant2\), \(x\nmid y\), \(x\mid y+1\) \[\begin{align} (x+y)^2&=(6+5)^2 \\&=11^2 \\&=121 \\&\equiv 1 \pmod{6} \end{align}\] Tan Kenneth · 2 years, 2 months ago

Log in to reply

@Tan Kenneth Thanks, I came up with it in the car, so who knows. And I coded it, most of them didn't work. It's basically y if (y+1) or (y-1) mod x equals 1? Thanks Zaid Baig · 2 years, 2 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...