Tagged Questions
2
votes
4answers
61 views
Solve for $x$: $4x = 6~(\mod 5)$
Solve for $x$: $4x = 6(mod~5)$
Here is my solution:
From the definition of modulus, we can write the above as $ \large\frac{4x-6}{5} = \small k$, where $k$ is the remainder resulting from ...
1
vote
2answers
37 views
Find the values of $p$ such that $\left( \frac{7}{p} \right )= 1$ (Legendre Symbol)
Show that if $p$ is an odd prime coprime to $7$, then $\left( \frac{7}{p} \right) = 1$ if and only if $p \equiv \pm 1, \pm 3,$ or $\pm 9 \pmod{28}$. HINT: If $p$ is an odd prime, determine which ...
0
votes
3answers
54 views
Modulo number multiplied by constant
I am proving that for any integers $a,b$, it is impossible to write $a^2 - 5b^2 \equiv 2 \mod 4$. The first thing I have said is to assume $a,b$ are both even. So I have said
$$a,b \equiv 0 \, \, ...
2
votes
1answer
82 views
Find the modulo between two large number
I'm trying to find
3185^2753 mod 3233
to decode a RSA message. How can I do it? What is the theorem behind this, if any?
The original question is:
What is ...
0
votes
4answers
46 views
Prove $2^k+1$ divisible by 3 for odd K
Prove $2^k+1$ divisible by 3 iff $k$ is odd number.
Since I need to prove both direction looks like if I need to prove it's divisible by 3 it's by induction and the other side by congruence..am I ...
5
votes
2answers
129 views
How to prove that for all $m,n\in\mathbb N$, $\ 56786730 \mid mn(m^{60}-n^{60})$?
How to prove $\forall m,n\in\mathbb N$:
$$ 56786730 \mid mn(m^{60}-n^{60})?$$
Thanks in advance.
2
votes
3answers
120 views
Modular homework problem
Show that:
$$[6]_{21}X=[15]_{21}$$
I'm stuck on this problem and I have no clue how to solve it at all.
1
vote
1answer
69 views
Square root congruence equation: solving for the modulus
I'm trying to solve a system of the type
$a^2 \mod n \equiv b\\
b^2 \mod n \equiv c\\
c^2 \mod n \equiv d\\
...$
Where $n = p q$ for some primes $p$ and $q$. I know how to solve these systems ...
2
votes
3answers
70 views
Arithmetic series has first term
An arithmetic series has first term a and common difference d.
The sum of the first 31 terms of the series is 310
a) Show that a + 15d = 10
b) Given also that the 21st term is twice the 16th ...
2
votes
4answers
123 views
Solving $13\alpha \equiv 1 \pmod{210}$
Determine $n \in \mathbb N$ among $12 \leq n \leq 16$ so that $\overline{n}$ is invertible in $\mathbb Z_{210}$ and calculate $\overline{n}^{-1}$.
In order for $n$ to be invertible in $\mathbb ...
3
votes
3answers
108 views
Solve $x^{11}+x^8+5\equiv 0\pmod{49}$
Solve $x^{11}+x^8+5\pmod{49}$
My work
$f(x)=x^{11}+x^8+5$
consider the polynomial congruence $f(x) \equiv 0 \pmod {49}$
Prime factorization of $49 = 7^2$
we have $f(x) \equiv 0 \mod 7^2$
Test ...
2
votes
1answer
54 views
modular arithmetic question help
I have to solve $x$ given the next three equations:$x=2\mod 7$, $x=3\mod 11$ and $x=4\mod 13$.
What I tried: first try to find $x$ that satisfies the first two equations. There are $a,b\in \mathbb Z$ ...
1
vote
1answer
65 views
Show that $2^{341}\equiv2\pmod{341}$
Show that $2^{341}\equiv2\pmod{341}$
My work:
Prime factorization of $341 = 31\cdot11$, thus $2^{11\cdot31}\equiv2\pmod{31\cdot11}$
$2^{341} = 2=2(2^{340}-1)$, we have $2^{340}\equiv1\pmod{341}$
...
2
votes
3answers
90 views
high power congruences finding $x$
trying to solve:
$$x^{13} \equiv 11 \pmod{135}$$
I came to the fact that $x = 11^{59}$ but its in mod $72$ and needs to be converted to mod $135$
any suggestions? I'm not sure how to change it to ...
2
votes
3answers
116 views
Proving $4^{47}\equiv 4\pmod{12}$
I know this is a simple exercise, but I was wondering if I can make the following logical jump in my proof:
We see that $4\equiv 4\pmod{12}$ and $4^2\equiv 4\pmod{12}$. Then we can recursively ...
1
vote
3answers
101 views
Solving simultaneous linear congruences
(a) $x≡5\pmod 7\;\;,\; x≡7\pmod{11}\;\;,\;\;x≡3\pmod{13}$
(b) $x≡3\pmod{10}\;\;,\;\; x≡8\pmod{15}\;\;,\;\;x≡5\pmod{84}$
for (a) I have a rough idea how to do it, its like:
$n_1=7,n_2=11,n_3=13$ ...
3
votes
2answers
93 views
Calculate $20^{1234567} \mod 251$
I need to calculate the following
$$20^{1234567} \mod 251$$
I am struggling with that because $251$ is a prime number, so I can't simplify anything and I don't have a clue how to go on. Moreover how ...
6
votes
1answer
86 views
Tell wether $(1234657)! +1 \equiv_{11111} (7654321)! -1$ is true or false
I have to tell if the following is true or false:
$$(1234657)! +1 \equiv_{11111} (7654321)! -1$$
so by definition we can rewrite the previous equivalence as:
$(1 \cdot 2 \cdot \ldots \cdot 11110 ...
0
votes
0answers
51 views
Using modular arithmetic for the decimal byte ring, compute the following…
Using modular arithmetic for the decimal byte ring,
Compute: $5 + (- 175+222)*13 = ~?$
This is a question I'm supposed to understand before I start a assembly language course next semester. Can ...
-1
votes
1answer
66 views
Compute Using modular arithmetic for the decimal byte ring,
Using modular arithmetic for the decimal byte ring,
Compute: 5 + (- 175+222)*13 =
This is a question I'm supposed to understand before I start a assembly ...
1
vote
2answers
64 views
Modular arithmetic: confusion one the $mod$ operator.
Suppose I have $a\equiv b \text{ (mod $c$)}$ and I just know $c$. I want to know, say $b$. Is this the same as $a$ mod $c$? If so, why?
I think I confuse the congruence with the equality symbol, ...
2
votes
1answer
85 views
0
votes
1answer
217 views
how many 2x2 matrices are invertible in mod p
I am trying to solve this problem for homework but unable to get anything. The question is to find the number of invertible 2x2 matrices in mod p? Each entery can bee from the set ...
2
votes
2answers
86 views
modular multiplicative inverse
I have a homework problem that I've attempted for days in vain... It's asking me to find an n so that there is exactly one element of the complete residue system mod n that is its own inverse apart ...
1
vote
6answers
104 views
Simple linear congruence question
Where did the following argument go wrong? (The correct answer in $\mathbb{Z}_{100} $is just $81$.)
Working mod 100:
$$21x\equiv1$$
$$105x\equiv5$$
$$5x\equiv5$$
$$x\equiv1,21,41,61,81$$
Thank you.
1
vote
1answer
133 views
Computational Complexity of Modular Exponentiation
The following was posted from a lecture:
"($a^n \bmod N$) has a runtime complexity of $\mathcal{O}(n*|a|*|N|)$ using the brute force method.
$Z_1 = a \bmod N$
$Z_2 = (aZ_1) \bmod N$
$Z_3 = (aZ_2) ...
2
votes
1answer
83 views
What is the modular representation of an integer?
What is the modular representation of an integer using a set of primes?
More specifically, a problem on my homework asks to convert 49 to a modular representation using primes 7,11,13,17.
Would ...
2
votes
3answers
725 views
How to solve system of equations with mod?
I'm trying to solve for $a$ and $b$:
$$5 \equiv (4a + b)\bmod{26}\quad\text{and}\quad22\equiv (7a + b)\bmod{26}.$$
I tried looking it up online, and the thing that seemed most similar was the Chinese ...
1
vote
1answer
116 views
doing an attack on elgamal using pycrypto, how do i solve for this random K? [closed]
I am working on a cryptography homework, doing an elgamal attack. I am using pycrypto's package.
$(a, b) = encrypt(plaintext, K)$
where
$a = g^K \bmod p$
$b = (M * (y^k \bmod p)) \bmod p$
note* ...
0
votes
1answer
47 views
Transfering algorithm into equation(s) and solving it?
Could someone for me try to transform algorithm that is in next pdf into equation(s):
http://arxiv.org/pdf/math/0507011?
For instance take example from page 6 for divisibility of number 16762 and try ...
2
votes
1answer
50 views
Exponential modular equation
I am having some trouble in proving that the only solutions to
$$ -2^{m-1} \equiv m \pmod{7} $$
are $m \equiv 3,5, 13 \pmod{42}$.
What I tried to use:
If $-2^{m-1} \equiv m \pmod{7}$, then ...
1
vote
2answers
143 views
Solving Linear Congruence
Ok, I found a lot of questions asking about solving $a = b \pmod c$ where you could divide $a$ and $b$ by some $x$ where gcd$(x, c) = 1$. How do you solve when this is not the case?
Suppose I have ...
2
votes
4answers
137 views
How many solutions does equation $6x=14 \bmod 35$ in $\mathbb{Z}/35\mathbb{Z}$ have?
Yes, this is a homework problem. And no, I'm not asking for the answer to this.
I just want to understand how to tackle this type of problem. What are the steps towards finding the solutions? My ...
0
votes
3answers
457 views
How is 3 modulo 5 = 3
Just tried googling but couldn't find any example, but how 3 % 5 = 3
Googled it
2
votes
4answers
349 views
Checking if a set is closed under modular multiplication
I have to check if the set {1, 3, 7, 9, 11, 13, 17, 19} forms a group under multiplication modulo 20, and the only idea that I've had so far is: attempt brute force on all the elements (multiplying ...
1
vote
2answers
96 views
In modular arithmetic is the concept of “increasing” well defined?
If there is a function $f(x) = x\bmod n$ and, whenever $0\leq x_1\lt x_2\lt n$, we have $f(x_1)\lt f(x_2)$, can we say that $f$ is increasing?
Also, when finally I prove that $f(x)$ is increasing, ...
5
votes
1answer
241 views
calculating with residue classes in $\mathbb{Z}{/5\mathbb{Z}}$
How to calculate with residue classes in $\mathbb{Z}{/5\mathbb{Z}}$?
$- \overline x \neq \overline x$ but $- \overline x = \overline{5-x}$
$\overline x + \overline y = \overline{x+y}$
$\overline x ...
3
votes
3answers
472 views
Finding the least significant digit of a large exponential.
I am trying to find the least significant digit of $17^{{17}^{17}}$. I know that I need to use to use the properties of modular arithmetic and mod base 10, but I am not sure how to go about it.
...
0
votes
3answers
78 views
Does $a \equiv b \pmod n$ mean $n \mid a - b$ or $n \mid b -a$
If I have
$a \equiv b \pmod{n}$,
it means
$n \mid b - a$.
But can you write it as
$n \mid a - b$
as well?
5
votes
5answers
518 views
Largest integer that can't be represented as a non-negative linear combination of $m, n = mn - m - n$? Why?
This seemingly simple question has really stumped me:
How do I prove that the largest integer that can't be represented with a non-negative linear combination of the integers $m, n$ is $mn - m - n$, ...
0
votes
1answer
97 views
why the increment doesnt affect the randomness?
I'm doing some homework and I need to answer why the increment (b) doesn't affect randomness in the mixed congruential method.
The formula is
$$X_{n+1} \equiv (a X_n + b) \mod m$$
1
vote
2answers
198 views
How do I inverse a bijective modulo function?
In my discrete maths homework, I'm being asked to find the inverse of a cipher function:
$$f(p) = (3p + 5) \bmod{26}$$
$f(p)$ accepts natural integers of the range ${0,1,...,25}$ (where A = $0$ and ...
1
vote
1answer
242 views
Breaking RSA in a special case
This is a part of homework assignment, and I am stuck.
The RSA signature is being calculated using Chinese Remainder theorem technique. Find the detailed description here.
Public and private keys are ...
1
vote
1answer
953 views
fastest way to calculate the remainder (modular)
I'm creating a computer application in which I need to be able to calculate the remainder of large numbers (more then 30 digits). I was searching the Internet for the fastest way to calculate this, ...
1
vote
2answers
203 views
Modular equations system
I have the following task - I have to find all a for which the following system has a solution:
$x \equiv 1\pmod 2$
$x \equiv 2\pmod 3$
$x \equiv a\pmod 5$
I ...
0
votes
1answer
142 views
Modular Arithmetic [duplicate]
Possible Duplicate:
Modulo Arithmetic
How would you find x in a modulo arithmetic expression x^e mod p knowing only e and p?
e is an integer, 0 ≤ e < p, that is relatively prime to p-1; ...
0
votes
2answers
179 views
How to find $x$, knowing $e$, $p$, and $x^e\bmod p$?
How would you find $x$ in a modulo arithmetic expression $x^e \bmod p$ knowing only $e$ and $p$?
$e$ is an integer, $0 \leq e \lt p$, that is relatively prime to $p-1$; and $x$ is an integer, $0 \leq ...
2
votes
2answers
140 views
Perfect square. Factorising problem
What is the sum of all positive integers $n$ for which $2^n + 65$ is a perfect square?
2
votes
3answers
236 views
Efficient way to find $a^b \bmod {n}$
I am not sure whether or not this is a duplicate question. I'm wondering what is an efficient way to compute
$$x \equiv a^b \bmod{n}$$
where $a,b,n \in \mathbb{Z}$ and $a,b < n$?
For example say I ...
2
votes
1answer
981 views
Simplifying or easily evaluating a large exponent in a mod number system
For an assignment, I've been asked to evaluate $7^{10507} \bmod 13$.
I know it's possible to do this using binary fast exponentiation - in fact the question refers to a previous question where I ...
