1
vote
1answer
21 views

(Counting problem) very interesting Modular N algebraic eqs - for combinatorics experts

We have some attempt to numerically solve this math problem, which means that we like to count the number of independent solutions of this set of six of modular N algebraic equations: $$ (1) x_1 ...
0
votes
1answer
47 views

System of linear equations over $\mathbb{Z}_p$

Something like this: $$ \begin{cases} x_1+4x_4=1\\ x_1+2x_2+4x_3=3\\ 2x_1+2x_2+x_4=1\\ x_1+3x_3=2 \end{cases} $$ over $\mathbb{Z}_5$ I'm fine with solving it in regular $\mathbb{Z}$ but have no idea ...
1
vote
1answer
92 views

How do I row reduce a matrix mod 26 when it is singular mod 26?

Cryptography assignment question: matrix $A$ is \begin{equation} A = \left(\begin{array}{ccc} 1 & 0 & 0 \\ 1 & 3 & 1 \\ 0 & 2 & 5 ...
2
votes
3answers
60 views

Finding the remainder when $1.1!+2.2!+3.3!+ … +10.10! +2$ is divided by $11!$

Find the remainder when $1.1!+2.2!+3.3!+ ... +10.10! +2$ is divided by $11!$ An attempt: Rearranging: $$\frac{1}{11!}+\frac{2.2!}{11}+\frac{3.3!}{11} \cdots +\frac{10.10!}{11}+\frac{2}{11!}$$ ...
0
votes
1answer
40 views

Combinatorics and Linear Alegbra

$$T = \{1011, 0112, 2101\} \subset Z_3^4$$ Is there any efficient way to find the span for set T other than checking all 27 possibility? If so, how to do it?
1
vote
1answer
55 views

Probabilistic Algorithm for Determining if a Matrix is Nonsingular.

I was reading through Problem-Solving Through Problems and ran into the following problem, Determine whether the following matrix is singular or nonsingular: $$ \begin{bmatrix} 54401 & 5768 ...
2
votes
0answers
323 views

How can I solve system of linear equations over finite fields in WolframAlpha?

Is it possible to solve system of linear equations over finite fields using Wolfram Alpha? If yes, how can I do that? Let us take a system $x+y+z=0$, $2x+y+2z=0$, $x+3y+z=0$. If I want to solve this ...
4
votes
2answers
157 views

Solving a system of equations using modular arithmetic

I am trying to implement a solver for the game lights out. You have a grid of lights, when you click on one of them the light you clicked and its four neighbours change colour, with the light starting ...
0
votes
1answer
76 views

Bases of $\mathbb{F}_p^2$

Let $\mathbb{F}_p$ be a prime field, and let $V=\mathbb{F}_p^2$. Prove: The number of bases of V is equal to the order of the general linear group $GL_2(\mathbb{F}_p)$
8
votes
1answer
83 views

Finding the generators of a subgroup of $\mathrm{SL}_2(\mathbb Z)$

I am trying to solve the following problem: Let $T_{ij}(c)\in\mathrm{SL}_2(\mathbb Z)\ (i\neq j)$ be the elementary matrix which represents the elementary row operation of adding the $j$-th row ...
1
vote
1answer
21 views

generating a vector given other vectors in modulo 11

how to show that vector $X4=\begin{bmatrix}0 \\ 2 \\ 1 \\ 1\end{bmatrix}$ can be generated with $X1=\begin{bmatrix}9 & 1 & 0 & 0\end{bmatrix}$ $X2=\begin{bmatrix}8 & 0 & 1 & ...
1
vote
1answer
90 views

how to interpret theorem about polynomial factorization over modulo ring?

polynomial $X^n+a_1X^{n-1}+...+a_n \in \Bbb Z_2[X]$ doesn't have linear factors $\iff a_n(1+\sum a_i) \neq 0$. How then $f(X)=X+1$ can has no linear factors? Doesn't the condition expands to ...
3
votes
1answer
116 views

Solve a system of linear congruences

I have this system: $$ \begin{align} a_{11} x_1 + a_{12} x_2 + \ldots + a_{1n} x_n &= b_1 \mod p \\ a_{21} x_1 + a_{22} x_2 + \ldots + a_{2n} x_n &= b_2 \mod p \\ \vdots \\ ...
1
vote
1answer
103 views

Matrix inversion help

If $g(n)$ is an integer functions periodic in $a$ And $\phi(a)$ is eulers totient function And $[r_1,r_2,r_3,...r_{\phi(a)}]$ are the postive integers less then $a$ coprime to $a$ With ...
11
votes
5answers
300 views

Why are there$ 736$ $2\times 2$ matrices $(M)$ over $\mathbb{Z}_{26}$ for which it holds that $M=M^{-1}$?

I'm currently trying to introduce myself to cryptography. I'm reading about the Hill Cipher currently in the book Applied Abstract Algebra. The Hill Cipher uses an invertible matrix $M$ for ...
0
votes
0answers
115 views

Solving systems of linear congruences with rational coefficients

Is there any way to solve for $x$ in a system of linear congruences with rational coefficients in the following form? $$Ax \equiv b\pmod 2, \space where\space A \in \Bbb Q^{n,m}, b \in \Bbb Q^m$$ ...
2
votes
1answer
204 views

System of Linear Equations using Mod

I just want to check that I did a certain problem correctly. This is it: $$a+b=3 \pmod{26}\\2a+b=7 \pmod{26}$$ Solve for $a$ and $b$ Now I setup the augmented matrix: $$\left[ \begin{array}{ccc} 1 ...
0
votes
1answer
89 views

integer transform

Let be $X$ an integer set: $X=\{0,1,2,\ldots,63\}$. Let be $(x,y)$ two elements from $X$ ($(x,y)\in X \times X$). I want to know if exist two transforms $T_1 :X \times X \to X$ and $T_2 :X \times X ...
0
votes
3answers
56 views

elementary congruence statement proof

it is me again :), i am trying to prove this statement of congruence, the statement is as follows: $a \equiv b \mod m \Longrightarrow a^{k} \equiv b^{k} \mod m $ for all $ k \in \mathbb{N}$ i ...
1
vote
2answers
66 views

congruence theorem prove

i am trying to prove this statement of congruence which is not really hard, but i am stumbling across the simple step. statement: $a \equiv b \mod m \land c \equiv d \mod m \Longrightarrow ac ...
1
vote
2answers
342 views

Solving $4$ simultaneous linear equations modulo $26$

I'm trying to solve these equations to solve a ciphertext which is encrypted by the Hill Cipher. I tried to solve these equations algebraically. (First choose two of them and try to eliminate one ...
2
votes
1answer
506 views

Modular Arithmetic over a Matrix

What are the rules for modular arithmetic when multiplying two matrices? I want to calulate $C = AB \mod{n}.$ Aside from the obvious way of performing the modulo after the multiplication, when and ...
6
votes
2answers
445 views

Find all linearly dependent subsets of this set of vectors

I have vectors in such form (1 1 1 0 1 0) (0 0 1 0 0 0) (1 0 0 0 0 0) (0 0 0 1 0 0) (1 1 0 0 1 0) (0 0 1 1 0 0) (1 0 1 1 0 0) I need to find all linear ...
1
vote
1answer
96 views

MOD functions spanning the vector space $\mathbb{R}^{\{0,1\}^n}$

Let $MOD_{a,c}^r:\{0,1\}^n\to\{-1,1\}$ denote the function $$MOD_{a,c}^r(x)=\cases{-1 \ a\cdot x+c\equiv0\ (\text{mod r}) \\ 1 \ \text{else }}$$ Here $\cdot$ is the usual dot product. I want to ...
2
votes
1answer
366 views

Existence of solution of a modular system of linear equations

I want to know if a given system of linear integer equations has an integer solution. I know it is the case if and only if it has a solution modulo $n$ for all integer $n$. What I do not know is when ...
4
votes
1answer
67 views

Calculating with inverses in $\mathbb Z_7$

I want to calculate $\frac{\overline{2}}{\overline{3}}$, $\frac{\overline{1}}{\overline{9}}$, $\frac{\overline{32}}{\overline{9}}$ in $\mathbb{Z}_7$. About first example my book says: ...
2
votes
1answer
159 views

Complexity of Gauss elimination over ring $Z_n.$

Is there some polynomial upper-bound for Gauss elimination over ring $Z_n$? I'm interested in polynomial bound depending from size of matrix and $\log n$. I also have the same question about the ...
2
votes
3answers
883 views

I don't understand why the inverse is this?

my question is related to matrix inverting and Hill cipher(you don't have to know what it is to help me) My teacher gave me an example. First we have a matrix (the key matrix) that multiplied by a ...
1
vote
2answers
924 views

What are the rules for basic algebra when modulo real numbers are involved

That is real numbers modulo an integer. I'm just interested in shuffling around +-*/ operations. If a concrete example helps here's my current problem. (I'm from a programming background so there's ...
1
vote
1answer
345 views

How can I solve a vector equation in Z2?

I have a equation with 256 variables * 256-dimensional vectors in $\mathbb{Z}_2 $: $$ x_1 \cdot \left(\begin{array}{c} 1\\ 1\\ 1\\ \vdots\\ 0 \end{array}\right) + x_2 \cdot ...
2
votes
2answers
1k views

how to solve linear equations involving modulo?

In one of the programming work I am doing, I encountered a set of linear eqns. with modulo. I am putting it in simple format with only 2 variables, $$(a_{11}x + a_{12}y) \mod 8 = b_1$$ $$(a_{21}x + ...