Chinese Remainder theorem related stuff.

Question

kainui · Answer

I have a set of mutually relatively prime numbers $\{a_1, \dots, a_n\}$ and I define the product of all these to be $A = \prod_{k=1}^n a_k$.

Now I define the product of all except one of them to be: $A_n = \frac{A}{a_n}$

My suspicion is:

$$A_n^2 \equiv A_n \mod A$$

But I'm not sure how I could prove this and haven't found any counter examples yet.

ilovepuppieslol · Answer

@ganeshie8

kainui · Answer

The main sorta idea of this is that it allows us to use linear algebra inside of modular arithmetic since we have:

$$A_n A_m \equiv 0 \mod A$$
for $n \ne m$ and hopefully
$$A_n^2 \equiv A_n \mod A$$
this would let us do stuff similar to take dot products and cross products with the $A_n$ as basis vectors for our numbers since:

$$(x_1 A_1 + x_2 A_2)*(y_1 A_1 + y_2 A_2) \equiv x_1 y_1 A_1 + x_2 y_2 A_2 \mod A$$

This is a little off of what we want for a dot or cross product however if you look similarly at defining $\hat i^2 = \hat i$ and $\hat i \hat j = 0$ (orthonormal essentially)

$$(x_1 \hat i+ x_2 \hat j)*(y_1 \hat i+ y_2 \hat j) \equiv x_1 y_1 \hat i + x_2 y_2 \hat j$$

So just a starting point for something, not sure yet playing around.

kainui · Answer

Here's a concrete example, let's take the set:
$\{2,3,5\}$ that means we have:
$A_1 = 15$, $A_2=10$ and $A_3=6$ and of course $A=30$.

So we look at:
$$15^2 \equiv 15 \mod 30$$$$10^2 \equiv 10 \mod 30$$$$6^2\equiv 6 \mod 30$$

All true.

kainui · Answer

I might have made some progress here, but not sure.

$$A_n^2 \equiv (A+A_n)^2 \equiv (a_n A_n+A_n)^2 \equiv A_n^2 (a_n+1)^2 \mod A$$

Still need to show this is congruent to $A_n$ though but it's some kind of thing maybe. lol

kainui · Answer

Another idea, not sure if this is possible or not off hand I need to think about it but I'll throw it out there:

$$A_n^2 \equiv A_n \mod A$$
rearranges into:
$$A_n(A_n-1) \equiv 0 \mod A$$
BUT I also know:
$$A_n a_n \equiv 0 \mod A$$

So I think I can say to within a constant $k$ that:

$$k a_n \equiv A_n-1 \mod A$$?

kainui · Answer

Aha I see, so I have found here, #12 is what I used to get:
$$A_n^2 \equiv A_n \equiv 1 \mod a_n$$

Somehow gotta scale this up to $A_n^2 \equiv A_n \mod A$ though, so need to increase from $$A=a_n A_n$$

ilovepuppieslol · Answer

i have no idea what you are saying @Kainui

ilovepuppieslol · Answer

what do the A's stand for

kainui · Answer

@ILovePuppiesLol in my second post I explain what the A and $A_n$ are. But it's a bit abstract, so I made an example a bit further on with 2, 3, 5 as the example $a_n$. I start that post off with "Here's a concrete example..." so check that out.

Or just ask if there are words you don't know the meaning of, just list all the words you're unsure of with a guess of what you think they mean like this:

apple - red orb thing?
potato - brown apple but less sweet I think also has eyes
etc...

ilovepuppieslol · Answer

okay, are you trying to prove this?

ilovepuppieslol · Answer

not sure what Mod stands for

kainui · Answer

Yeah trying to prove that $A_n^2 \equiv A_n \mod A$ haha.

mod means you only care about the remainder of the stuff when you divide by A. It's kind of a complicated topic but it's the same as saying things like "even + even = even" and "odd * even = even" or how clocks are only the numbers 1 to 12 and 13 wraps around to be 1 again.

ilovepuppieslol · Answer

so its true

kainui · Answer

I don't know, this is something I invented on my own and suspect; I have no idea if it's actually true but it seems like it should be.