1
vote
2answers
47 views

Show $4x^3 + y^3 = 792,864,313,578,917,724,246$ has no solution for $x, y \in \mathbb{Z}$.

I think it involves something about looking at the last digits of the number and/or modular arithmetic but I don't remember how to do this. Help?
1
vote
8answers
121 views

Calculate the last digit of $3^{347}$

I think i know how to solve it but is that the best way? Is there a better way (using number theory). What i do is: knowing that 1st power last digit: 3 2nd power last digit: 9 3rd power last digit: ...
2
votes
3answers
69 views

Find the remainder of $40^{314}$ divided by 91.

Here's what I have so far. $$x \equiv 40^{314} \mod{91}$$ $$\Rightarrow$$ $$x \equiv 40^{314} \mod{7}$$ $$ x \equiv 40^{314} \mod{13}$$ Then by FLT, $$40^6 ≡ 1 \mod{7}$$ $$40^{12} ≡ 1 \mod{13}$$ ...
1
vote
4answers
40 views

How to find $k$ in $6^{k} \equiv 2 \mod {13}$

Find for which $k$ is $6^{k} \equiv 2 \mod {13}$ I'm having trouble with these types of question in my cryptography class. This is part of Diffie–Hellman algorithm for calculating a shared key. ...
1
vote
1answer
19 views

modular arithmetic problem (when solving elliptic curves)

Given E: (elliptical curve) $y^2 = x_3+2x+2 \bmod 17$ Recall: $y^2 = x^3+ax+b$ point $P=(5,1)$ Compute: $2P = P+P = (5,1)+(5,1)= (x_3,y_3)$ Now the formula used here is slope $m = \dfrac{3x_1^2 ...
0
votes
0answers
21 views

How to find p such that 1/p has a repeating decimal with a specified period

Alright, so I know a bit of information about the problem but I'm having trouble tying it all together. I know: if gcd(n,10)=1 then 1/n has a repeating decimal expansion. 10^3 = 1 mod p 1/p = ...
-2
votes
3answers
83 views

Find the least positive integer with remainders 1,2, and 3 when divided by 7,8, and 9 respectively.

a. Find the least positive integer with remainders 1,2, and 3 when divided by 7,8, and 9 respectively. The three congruences are $ x \equiv 1 $ (mod 7) $ x \equiv 2 $ (mod 8) $ x \equiv 3 $ (mod 9) ...
2
votes
1answer
71 views

Abstract Algebra Computation

Compute: $3^{47}$ mod $23$ $3^{49}$ mod $7$ $2^{2^{17}}$ mod $23\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$ hint: compute first $2^{17} + 1$ mod $19$ This is the first time I've had to ...
0
votes
2answers
46 views

Primes and Inverses of an integer

I have the following question which I do not understand. Here it is: Consider the primes $5$, $7$ and $11$ as n. For each integer from $1$ through $n - 1$, calculate its inverse. I do not ...
1
vote
2answers
38 views

Modular arithmetic question related to the fundamental theorem

Somewhat of an unusual homework problem that my professor assigned that I can't wrap my head around. We are only considering the positive numbers congruent to 1(mod 4), that is, other numbers do not ...
1
vote
3answers
89 views

Prove that, given integers a, b, and c such that a mod 6 = 3, b mod 8 = 3, and c mod 10 = 3, (a + b + c) mod 6 is odd.

I need to prove that, given integers $a$, $b$, and $c$ such that $a\mod6=3$, $b\mod8=3$, and $c\mod10=3$ then, $(a + b + c) \mod6$ is odd. Here's what I have tried. By using the definition of mod ...
0
votes
2answers
68 views

How to check if a function is an homomorphism?

For example: Let $$f:\mathbb{Z}_{60} \rightarrow \mathbb{Z}_{12} \times \mathbb{Z}_{20}$$ $$[x]_{60} \mapsto ([x]_{12} , [x]_{20})$$ Prove that it's well defined Check if it's a ring homomorphism ...
0
votes
1answer
64 views

ElGamal Public Key Cryptosystem and Digital Signature Scheme

I'm tryting to understand how ElGamal algorithm works, and I got the following example, and I couldn't understand one part of this: A) P=23, g=5. B) x=3, then y=10 (for 53 mod 23=10 ). C) Sign for ...
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
5answers
81 views

$4011x+42053 \equiv 2x-782398 \pmod {10}$

$4011x+42053 \equiv 2x-782398 \pmod {10}$ $10|(4011x+42053-2x+782398) \space \rightarrow \space 10|(4009x + 824451)$ $\rightarrow\space 4009x\equiv -824451 \pmod {10}$ I am dubious about this next ...
2
votes
3answers
112 views

Verifying that $2^{44}-1$ is divisible by $89$

As the title, I was asked to show that $2^{44}-1$ is divisible by $89$. My first attempt is to change the expression into $(2^{22}-1)(2^{22}+1)$. Then further simplified it into ...
1
vote
1answer
51 views

Minimum number of rows in a mod 12 multiplication table

Minimum number of rows you would need to write out in a mod 12 multiplication table to guarantee you wrote out an element with an inverse? I would think this would be just one row as 1 is its own ...
0
votes
1answer
25 views

Calculate inverse modulo: $8^{-13}\pmod {29}$

How can I calculate $8^{-13}\pmod{29}$ ? I don't get how it works. Can I do it separately? So first $8^{-13}$ and then modulo $29$. And how can I calculate a negative power the quickest?
2
votes
3answers
31 views

Congruence equation problem

My problem says: Give solution to this problem of congruence, with all incongruent solutions according to the requested module and all integer solutions. $10x \equiv 15 \mod 35$ But I can not ...
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?
2
votes
1answer
66 views

Irreducible 3rd degree polynomials over $\mathbb{Z}_3$ field?

I want to find all irreducible polynomials over $\mathbb{Z}_3$ field which have the form $x^3 + a_2 x^2 +a_1 x + a_0$. My thought process: Third degree polynomial is irreducible if it has no roots ...
5
votes
1answer
48 views

$x;y;z\in \mathbb{Z}$ such that $(x-y)(y-z)(z-x)=x+y+z$. Prove that : $27\mid x+y+z$

Let $x;y;z\in \mathbb{Z}$ such that $(x-y)(y-z)(z-x)=x+y+z$. Prove that : $27\mid x+y+z$ Thanks :) P/s : I don't have any ideas about this problem..!!
1
vote
0answers
47 views

Could Someone Just Verify This Proof for Me? (Euler's Theorem)

I came up with this proof for my number theory class. Is it valid? Proposition: $u\in U_m \Rightarrow u^{\varphi(m)}=1$ (Where $U_m$ is the multiplicative group of integers modulo $m$) Attempted ...
1
vote
2answers
25 views

Modular Arithmetic Homework

Find an integer $ m \ge 2 $ so that the equation $ x^2 \equiv 1 $ in $\mathbb{Z}/ m$ has more than two solutions. In a previous part I proved that there are two solutions $x=1,-1$ when $m$ is prime. ...
0
votes
1answer
80 views

How do you solve linear congruences with three variables.

Given \begin{cases} x+y+z &\equiv 1 \pmod{10} \\ x+2y+3z &\equiv 2 \pmod{10} \\ 2x+3y+6z &\equiv 3 \pmod{10} \end{cases} find $x,y,z$. How does one solve such a system of ...
4
votes
1answer
165 views

Square root algorithm in modulo $n = pq$

I've been stuck in this problem quite a bit. I have to find an efficient algorithm wich, given: $$ p = 4k+3\\ q = 4m+3\\ p,q \hspace{2mm} \text{odd primes}\\ a\in \mathbb{N} $$ verifies if there ...
0
votes
1answer
54 views

What is the identity for ab=2ab (mod 7)?

Using elements 1, 3, 5 write out a Cayley table. The operation for the table is ab = 2ab. For example 5*4= 5*4*2= 40 congruent to 5 (mod 7). What is the identity for this table?
0
votes
2answers
28 views

Smallest integer x s.t. x! congruent to 0 (mod 216)

By guess and check I found x to be 9, but is there a more general way to solve this?
1
vote
2answers
73 views

Find the smallest integer x s.t. x congruent to 1 (mod 1,2,3,4,5,6,7,8,9,10)

Don't really understand this question. If this is asking to find an x for each mod then the answer would be just be x+m...If this is asking to find an x that satisfies all mods, then this cant be ...
0
votes
2answers
54 views

Solving $4^{667} ≡ x \pmod{13}$ without Eulers totient theorem or CRT

Does anyone know any efficient ways to solve this without Euler's Totient Theorem or Chinese remainder theorem?
2
votes
2answers
280 views

How to compute $2^{\text{some huge power}}$

I have to compute $$2^{p-1} \mod p$$ and show by Fermat's little theorem that $p$ isn't prime. I know what the question is asking but I'm not sure how to reduce the exponent on $2^{p-1}$ to a more ...
2
votes
3answers
158 views

Divisibility problem with modular arithmatic

Here's the question: "When an integer $n$ is divided by 6, the remainder is 5. What are the possible values of the remainder when $9n$ is divided by 8?" I'm not entirely sure how to decipher this ...
3
votes
3answers
73 views

$ 7^{50} \cdot 4^{102} ≡ x \pmod {110} $

The way I would solve this would be: $$ (7^3)^{15} \cdot 7^5 \cdot (4^4)^{25} \cdot 4^2 $$ and take it from there, but I know that this is most likely in an inefficient way. Does anyone have more ...
0
votes
2answers
186 views

Quicker way to solve 10! congruent to x (mod 11)

I am new to modular arithmetic and solving congruences and the way I went about this was to write out $10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot2$. Mulitply numbers until I get a number ...
1
vote
1answer
92 views

Prove that there exists only 2 solutions for $x^2 \equiv 9 \pmod {p^k}$, ($p$ an odd prime > 3 and $x$ a natural number < $n$)

It appears that the only two solutions are always $3$ and $p^k-3$, I want to prove this, here has been my approach, I think I am close but just missing something, would really appreciate any help!!! ...
0
votes
1answer
50 views

Prove that for $n=2^k$, $(k \ge 3)$ there are 4 natural numbers less than $n$ that satisfy $b^2 \equiv 9 \pmod n$.

I think I am close to proving this, but just need a bit of help with some gaps in my understanding. I found using a recursive function in a small program that it seemed that for $k \ge 3$, I always ...
1
vote
0answers
217 views

How many ring homomorphism are there from $\mathbb{Z} / 12\mathbb{Z}$ to $\mathbb{Z} / 20\mathbb{Z}$? Find the image and kernel of them.

How many ring homomorphism are there from $\mathbb{Z} / 12\mathbb{Z}$ to $\mathbb{Z} / 20\mathbb{Z}$? Find the image and kernel of them. The above is the question, this is my attempt at an ...
1
vote
2answers
50 views

Find a positive integer $x$ less than $105$ satisfying the following simultaneous congruence equations.

$$x=2 mod 3$$ $$x=3 mod 5$$ $$x=4 mod 7$$ I have only learnt modulo for 2 weeks so far... really basic theorems. My attempt using definitions of modulo From Equation 1, $3a=x-2 ...
0
votes
1answer
52 views

Divisibility question with 8th powers

so I was assigned a divisibility question for homework. Prove that $27195^8-10887^8+10152^8$ is divisible by $26460$. Am I supposed to use mods? I appreciate the help!
0
votes
0answers
147 views

Show that if $N$ is an odd prime, then there are exactly $\frac{N + 1}{2}$ quadratic residues in the set $\{0, 1, …, N - 1\}$.

Fix a positive integer $N > 1$. We say that $a$ is a quadratic residue modulo $N$ if there exists $x$ such that $a \equiv x^{2} \pmod{N}$. Show that if $N$ is an odd prime, then there are ...
4
votes
2answers
322 views

Show that there are exactly two values in $\{0, 1, …, N - 1\}$ satisfying $x^{2} \equiv a \pmod{N}$.

Fix a positive integer $N > 1$. We say that $a$ is a quadratic residue modulo $N$ if there exists $x$ such that $a \equiv x^{2} \pmod{N}$. Let $N$ be an odd prime and $a$ be a non-zero ...
1
vote
2answers
189 views

Solve the following system of simultaneous congruences:

\begin{gather} 3x\equiv1 \pmod 7 \tag 1\\ 2x\equiv10 \pmod {16} \tag 2\\ 5x\equiv1 \pmod {18} \tag 3 \end{gather} Hi everyone, just a little bit stuck on this one. I think I am close, but I must be ...
0
votes
0answers
99 views

How to Solve $x^a=b$ in $\mathbb{Z}/n$

I'm preparing for an exam by looking over old exams and have to exam questions of the same type but solved slightly differently. a) $x^{13} = 3 \bmod{47}$, given that $3^{37}=14$. (Answer: $x=32$) ...
1
vote
1answer
104 views

Modular equation with very large powers

I studying for a discrete mathematics exam and am stuck on this question: Find the value of the unique integer $x$ satisfying $0 \le x < 17 $ for which: $$ 4^{1024000000002} ≡ x \pmod{17} $$ I ...
5
votes
3answers
79 views

Evaluate $\sum\limits_{(m,n) \in D,m < n} \frac{1}{n^2 m^2} $ where $\gcd(m,n)=1$

i have no clue on how to evaluate: $$\sum\limits_{(m,n) \in D,m < n} \frac{1}{n^2 m^2} \text{ where }D = \{ (m,n) \in (\mathbb{N}^*)^2 \mid \gcd(m,n) = 1\} $$ If someone is able to give me a ...
2
votes
2answers
122 views

Math Parlor Trick

A magician asks a person in the audience to think of a number $\overline {abc}$. He then asks them to sum up $\overline{acb}, \overline{bac}, \overline{bca}, \overline{cab}, \overline{cba}$ and ...
2
votes
1answer
144 views

Prove “casting out nines” of an integer is equivalent to that integer modulo 9

Let $s(x)$ be an abstraction for casting out nines of integer $x$. For all integers $x$, prove $s(x) \equiv x$ mod $9$ I'm not asking for an answer more of a way to attack this problem. Can't think ...
2
votes
3answers
98 views

Prove that if $p_1,\dots,p_k$ are distinct odd primes then 1 has $2^k$ square roots $\mod m$ where $m$ is the product of the primes.

I think I am most of the way through this proof but I am stuck. Here was my approach: I looked at the square roots of $1$ mod $105$, and noticed that each one corresponded to one less than an integer ...
2
votes
1answer
192 views

Find the smallest possible integer that satisfies both modular equations

Find the smallest positive integer that satisfies both. x ≡ 4 (mod 9) and x ≡ 7 (mod 8) Explain how you calculated this answer. I am taking a math for teachers course in university, so I'm worried ...
0
votes
1answer
37 views

Solving Modular Equations With Identities

$4+2x≡7 \pmod 8$ Find all possible solutions and note any identities. Identify how you found the solutions. Explain what identities are.