Modular arithmetic (clock arithmetic) is a system of integer arithmetic based on the congruence relation $a \equiv b \pmod{n}$ which means that $n$ divides $b-a$.

learn more… | top users | synonyms

0
votes
1answer
14 views

Quadratic congruences in which modulus is divisible by constant term

There are two similar congruences: $$ x^2-6x\equiv16\pmod{512}\\ y^2-y\equiv16\pmod{512} $$ It is easy to see that the $\gcd$ of all three parts in both of them is $16$, $x$ and $x-6$ are even and one ...
3
votes
1answer
44 views

Question about how to prove $x^5\equiv x \pmod {10}$

I was trying to prove why $x^5\equiv x \pmod {10}$ for all natural numbers $x$. I saw a proof where they applied Euler's theorem to show this. They said that the totient function for $10$ is $4$. ...
3
votes
3answers
155 views

How to divide natural number N into M nearly equal summands?

How to divide natural number N into M nearly equal summands? For example, to divide 20 by 13, in geometric representation, I should get How to generate the sequence above? What is the name of ...
2
votes
1answer
58 views

Cryptography, discrete mathematics

I have got following example at the lecture, however we went through it quite fast. I understand the calculation of the following inverse modulo: 7 · 103 = 1 (mod 120). However here I am puzzled ...
0
votes
2answers
23 views

Verifying integer solutions to linear equations

Suppose I have the equation $B = \frac{8A - 29}{27}$, where $A$ and $B$ are integers. Then $27B = 8A - 29$, and so we have the linear Diophantine equation $8A - 27B = 29$. Using the extended ...
0
votes
0answers
156 views
+50

Why did Fermat care about characterizing primes on the form $p=x^{2}+ny^{2}$?

Im currently trying to figure out the genesis of quadratic reprocity by using Cox and Lemmermeyers books. I also got a copy of some works of Fermat but it is in German. It seems like there is some ...
0
votes
1answer
35 views

Listing the elements of $U(\mathbb{Z}_{54})$.

The set of all integers modulo $q$ is denoted by $\mathbb{Z}_q$. When equipped with multiplication modulo $q$, has the structure of a commutative monoid, the identity element being equivalence class ...
0
votes
0answers
15 views

Ring structure of tuples mod k

Consider a vector of n integers $$A= a_1, a_2, ... a_n$$ Such that for another vector $$B= b_1,b_2... b_n$$ $$AB^T \equiv 0 \mod k$$ For an integer k. I was playing around with these structures ...
0
votes
1answer
62 views

Use Pohlig-Hellman to solve discrete log

We have $$7^x = 166 \pmod{433}$$ I need to find $x$ using the Pohlig-Hellman algorithm.
2
votes
1answer
56 views

How to find fast modular exponentiation?

I need to find $$5448^{5^3} \pmod{11251}$$ and $$6909^{5^3} \pmod{11251}$$ fast? I couldn't calculate it with normal tricks.
0
votes
1answer
51 views

Finite fields and arithmetic

For every prime number $p$ and every positive integer $k$, there is a field with exactly $p^k$ elements. When $k=1$, it's just the integers$\bmod p^k$, and when $k>1$, it's not. So if I want the ...
3
votes
1answer
38 views

Diophantine equation involving factorial …

Question . Find all positive integer solutions to the equation below , $$(n-1)!+1=n^m$$ (i)observe that $n>1$ and $n$ is a prime number (if not we can choose a prime number $p<n$ such that $p|n$ ...
3
votes
2answers
42 views

When is a number square in Galois field p^n if it's not square mod p?

Here is the problem, that I'm stuck on. There is no square root of $a$ in $\mathbb{Z}_p$. Is there square root of $a$ in $GF(p^n)$? Well, it's certainly true that $$x^{p^n}=x$$ and $$x^{p^n-1}=1$$ ...
0
votes
0answers
37 views

Calculate the product of $p(x)q(x) \pmod{x^3 +1}$

I need to calculate the product of $(x^2 + 3x + 1)(x^2 + 4x + 3)\pmod{x^3 + 1}$, where the product is in $\mathbb{Z}_5[x]$. Is this problem as simple as just multiplying the two, which would be $4x^4 ...
1
vote
2answers
39 views

How to prove $x^{\phi(m)+1}\equiv x\pmod{p}$ [duplicate]

How do I prove that $x^{\phi(m)+1}\equiv x\pmod{p}$ when $m=pq$, two distinct primes? I kind of have an idea that it involves Euler's Theorem but it doesn't seem to be working as well as I wanted it ...
1
vote
2answers
47 views

Find the least positive integer $x$ that satisfies the congruence $90x\equiv 41\pmod {73}$

Find the least positive integer $x$ that satisfies the congruence $90x\equiv 41\pmod{73}$. It is clear that an attempt to write this out as $90x-41=73n,\exists n\in \mathbb{Z}$ won't be very ...
0
votes
2answers
31 views

Repeated squaring method

How do I use the repeated squaring method to calcualte 2^176 (mod 177)? I'm not sure, but is there something about the fact that 177 is 1 greater than 176 that makes this a problem?
3
votes
3answers
70 views

Find the remainder if $19^{55}$ is divided by 13.

The question, as stated in the title, is Find the remainder if $19^{55}$ is divided by 13. Here is my approach for solving this problem. I know that $19\equiv6$ (mod 13), so $19^{55}\equiv ...
0
votes
1answer
44 views

Find conditions on $m$ and $n$ that ensure that $f$ is a bijection.

Given: $X=\{0,1,2,...,m-1\}$, $f:X\to X$, $f(x)=nx \pmod m$. Find conditions on $m$ and $n$ that ensure that $f$ is a bijection. Progress It seems that $(m,n)=1$ but I can't prove that. I tried ...
2
votes
1answer
57 views

Prove Euler's Theorem when the integers are not relatively prime

How can I prove Euler's Theorem: $$x^{\phi(m)+1} \equiv x \pmod m$$ is still true when $x$ is not relatively prime to $m$? Edit: when m=pq where p and q are distinct primes
4
votes
2answers
239 views

How can I test if an element g is a generator of a group G with a known number of elements, N?

Let's say $G$ has $1000$ elements. Without looping through each $g^m$, how can I show that $g$ is a generator? I've deduced that I must prove that the order of $g = N$, or in this case $1000$, but I'm ...
0
votes
1answer
27 views

Primitive roots of $2^{16} + 1$ [duplicate]

I have a primitive root $ \alpha $ of a number $ p = 2^{16} + 1$. How can I show if $ \alpha^{3} $ and $\alpha^{14}$ are primitive roots as well?
3
votes
2answers
252 views

Is this a legitimate proof? If not, how to prove?

Question: Determine all natural numbers $n$ such that: $7 \mid \left(3^n - 2\right) \implies3^{n}\equiv 2\pmod{7}$ Multiply both sides by 7 $7 \cdot 3^{n}\equiv 7\cdot2\pmod{7}$ Divide both sides ...
4
votes
4answers
87 views

Determining the last two digits of $229^{10} +37^{10}$

Determine the last two digits of: $229^{10}+37^{10}.$ I do not want to use the Euler-totient function or the carmichael function please! Thanks
1
vote
1answer
60 views

Given a, b How many solutions exists for x, such that: $a \bmod{x}=b $

Given $a, b$. How many solutions exists for $x$, such that: $$a \bmod{x}=b $$ By example: $a = 21$ and $b = 5$ $21 \bmod{8} = 21 \bmod{16} = 5$ Then $x$ has 2 solutions
0
votes
1answer
27 views

how many solution can be found of the form $A \pmod{X} = B$ [duplicate]

$A$ and $B$ are given, How many $X$ can be found to make the following equation true? $$ A \pmod{X} = B $$ Is there any formula?
0
votes
1answer
35 views

Prove homomorphism and surjectivity of a function

I have a question about this exercise for my math study: Let $d, n \in\mathbb{Z}_{>0}$ with $d\mid n$. a) Prove that there is a homomorphism $g: (\mathbb{Z}/n\mathbb{Z})^*\rightarrow ...
1
vote
2answers
40 views

How does this proof that the square of an integer, not divisible by 5, leaves a remainder of 1 or 4 when divided by 5 work?

Below I have a part of a proof of the fact that the square of an integer, not divisible by $5$, leaves a remainder of $1$ or $4$ when divided by $5$. But I am wondering where does the part highlighted ...
0
votes
1answer
38 views

homomorphism and resideu classes

I have a question about how I have to do this exercise for my math study: Let d, n $\in$ $\mathbb{Z}$>0 with d|n. a) Prove that there is a homomorphism f: $\mathbb{Z}$/n$\mathbb{Z}$ $\rightarrow$ ...
0
votes
1answer
17 views

Negative Modulo confusion

$$ x \equiv -74 \ mod \ 31 $$ According to Google & Wolframalpha the answer is 19 Following the method in this answer and using this answer I get 12. Using my calculator with this answer yeilds ...
0
votes
1answer
24 views

Find inverse modulo when modulo is smaller than the number

I know how to use the Euclidean algorithm to find the inverse modulo in most cases, but I can't wrap my head around the calculations when the modulo is smaller than the number I'd like to find the ...
0
votes
0answers
25 views

Minimization problem involving a set of prime numbers and modular arithmetics

I'm a student working for curiosity on a general minimization problem where I suppose that there is no efficient algorithm for solving it. I'd like to ask for your valuable advice. Let $P$ be a set ...
1
vote
3answers
45 views

$\pmod{n}$, proving that they are no integer solutions

Prove $5a^2\equiv k \pmod{12}$, where $k\in \{0,5,8,9\}$. Hence show that the equation $24x^7 + 5y^2 = 15$ has no integer solutions. My lecturer used a table containing $a$, $a^2$, and $5a^2$ from ...
6
votes
1answer
123 views

Find the last digit of the exponent $x$.

Let \begin{align} p&=396543857870745963499374527519378569849832249490600276007703072957912\cdots\\ &\phantom{=}8049490077183813353745228056691 \end{align} This number is a 100-digit prime ...
0
votes
2answers
49 views

How to get last digit of $7^{7^7}$

I want to find the last digit of $7^{7^7}$. I found out already that $7^7$ (mod 10) last digit is 3. But how do I use that to get the last digit of the whole thing? Thanks
1
vote
1answer
29 views

Fermat's Little Theorem - Prim. Root - Find x

So I am studying for finals and I am not able to solve the problem: Let $p=3∗2^{11484018}−1$ be a prime with 3457035 digits. Find a positive integer $x$ so that $2^x \equiv 3 \mod p$ Any guidance ...
3
votes
1answer
30 views

Find an integer $x$ such that $2^x \equiv 3\pmod{p}$ given prime $p$

So I am studying for finals and I am not able to solve the problem: Let $p=3\times2^{11484018}−1$ be a prime with 3457035 digits. Find a positive integer $x$ so that $$2^x \equiv 3 \pmod p$$ Any ...
2
votes
2answers
27 views

How to solve this congruence?

Given that $6^{12} ≡ 16\pmod {109}$. Is there a $k$ such that $16^k ≡ 6 \pmod {109}$? If there is, then find all the $k$'s. Does anyone know how to do this? Thanks
1
vote
1answer
10 views

Equivalence Relation Properties

I have to define whether the following relation is symmetric, reflexive, and transitive. Define a relation R on Z as follows: (x, y) ∈ R if and only if x = |y|: This is my answer so far: Is ...
1
vote
1answer
53 views

Find the residue of $1!+2!+…+n! \pmod{m}$ for $m>n$

Find the residue of $ 1!+2!+........+n! \pmod{m}$ for $m>n$ $n,m$ are positive numbers and need not be primes. is there any known proof or result for this thanks
0
votes
0answers
31 views

Could this discrete logarithm problem be proved?

Given some values $X$, $Y$, $A$, $B$ and $p$, is there a way to show that there exists (or doesn't exist) an $n$ such that $X = A^n \mod{p}$ and $Y = B^n \mod{p}$? Alternatively, are there particular ...
0
votes
3answers
19 views

Congruences - proof problems

1) State what is meant by $a\equiv b \pmod n$. 2) Suppose that $a\equiv b \pmod n$ and $c\equiv d \pmod n$. Prove that i) $a+c\equiv b+d \pmod n$ ii) $ac\equiv bd \pmod n$ For question 1, ...
0
votes
1answer
19 views

System of congruences with not coprime numbers

I have a system of congruences, for example $ x \equiv 2 \mod 15$ $ x \equiv a \mod 21$ where $a$ is an integer to be determined. I have to find all the values of $a$ for which the system has ...
2
votes
1answer
33 views

Modulo a composite number same as modulo individual factors?

Can somebody please give me a hint why the following holds (or doesn't it?): if $r^2 \equiv a \mod n$ and $n = p * q$, then $r^2 \equiv a \mod p$ and $r^2 \equiv a \mod q$. I tried it with ...
0
votes
2answers
39 views

Properties of addition and multiplication modulo $m$

I was studying some number theory and I came across this theorem in a book, but unfortunately there was no proof of it. Can somebody tell me the proof? $$(a + b) \bmod m = ( (a \bmod m) + (b \bmod m) ...
0
votes
3answers
36 views

Solve for the unknown

$31x-21^{21} \equiv 21+31^{31} \pmod 5$ The provided answers are: $$ \left\{ 3,8,13,18,... \right. $$ but I don't know how to get there. Can someone walk me through this please?
-1
votes
2answers
55 views

Prove this using modular arithmetic [closed]

$For n \in N$ Prove that: $\prod\limits_{x\in Z^*_n} x= \pm 1$ Thanks in advance!
0
votes
0answers
17 views

Prove this relation

Solve this: $y^2+2=x^3$ or Prove that $y^2+2=x^3 => (x,y)=(3,\pm 5)$ I know that it could be obvious to some of you by trial and error but I need a methodical approach. Thanks in advance!
0
votes
0answers
20 views

congruence, please hepl me solve this

$$ x^4 + x + 3 = 0 \pmod{3^3} $$ I'm not sure how to this, I've tried many times but it never works for me :/ so, I hope someone will help me
1
vote
0answers
21 views

Euler's criterion and Legendre symbol

I am working on an exercise which is the following : Let be $n$ an odd integer and $b$ such as $b \wedge n = 1$, then $(\frac{b}{n}) \equiv b^{(n-1)/2} \mod n$. (*) If $n$ is divisible by the ...