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
43 views

Number of solutions of the congruence $x^p \equiv x\pmod p$

How do I show that $x^p \equiv x\pmod p$ has precisely $p$ solutions? I can use Lagrange's theorem and Fermat's little theorem.
2
votes
2answers
45 views

Use Euclid's algorithm to find the multiplicative inverse $11$ modulo $59$

I was wondering if this answer would be correct the multiplicative of $11$ modulo $59$ would be $5$ hence $5\cdot11 \equiv 4 \pmod{59}$. Is this correct?
0
votes
0answers
20 views

Modulus Syntax in congruences

So I have some homework that has a notation I've never seen before and I can't find any documentation myself. Our professor gave us problems like this ...
0
votes
0answers
58 views

Solving RSA cipher without calculator

I have a question: Encrypt the message UPLOAD using RSA with $n=3\cdot 31$ and $e =17$. My question is, how can I solve this with a calculator and in an efficient manner due to being in an exam ...
2
votes
5answers
65 views

Possible solutions of a diophantine equation: $p^2+pq+275p+10q=2008$

What are couples of prime integers that verify this diophantine equation: $$p^2+pq+275p+10q=2008?$$ I tried to solve this equation trough the rules of modular-arithmetic. I rewrite the equation as: ...
0
votes
2answers
41 views

Factorization in modular arithmetic

Is this expansion a legal step? $12^8\mod15 = 2^8 * 2 ^ 8 * 3 ^ 8\mod15$
0
votes
0answers
52 views

Collatz algorithm generalization try-out (Collatz k-algorithm)

Recently I have been reading about the Collatz conjecture here in Mathematics Stack Exchange, and also found the fantastic paper of professor Lagarias about it. Everything was so interesting (and I ...
0
votes
0answers
21 views

Number of times the loop is executed

Initially I have provided x and y and the value of x and y repeatedly calculated until at some point the sequence is start repeating. ...
0
votes
2answers
26 views

Problem in proof of: Show the order $d$ of $a$ modulo $m$ exists and $d\mid\phi(m)$

Theorem: Let $m\in\mathbb{N}$ and $a\in\mathbb{Z}$ satisfy $(a,m)=1$. Then the order $d$ of $a$ modulo $m$ exists, and $d\mid\phi(m)$. Proof: By Euler's theorem, one has $a^{\phi(m)}\equiv ...
0
votes
2answers
33 views

Order of Elements in $Z_{12}$

So I know all the orders of the elements in $(Z_{12},+)$ $|[0]| = 1$ $|[1]| = 12$ $|[2]| = 6$ $|[3]| = 4$ $|[4]| = 3$ $|[5]| = 12$ $|[6]| = 2$ $|[7]| = 12$ $|[8]| = 3$ $|[9]| = 4$ $|[10]| = ...
0
votes
1answer
44 views

Number Theory proving questions [closed]

Let $n$ be a positive integer such that $n \equiv 3 \pmod 4$. Prove that $x^2 \equiv -1 \pmod n$ is not solvable for integer $x$.
2
votes
1answer
46 views

$g^q-q$ and $g^q-gq$ are primitive roots modulo $q^2$

Let $g$ be a primitive root modulo an odd prime $q$. Then, both $g^q-q$ and $g^q-gq$ are primitive roots modulo $q^2$. I read this question somewhere and the first thing that came to my mind as a ...
8
votes
1answer
192 views

Reduction modulo p of a linear group over the rational numbers

A paper (http://arxiv.org/pdf/1407.3158v2.pdf) contains the following theorem: Suppose $\mathbb{G}$ is a connected, simply connected, semisimple algebraic group defined over $\mathbb{Q}$, and let ...
1
vote
4answers
34 views

How to solve modular equations

How to solve modular equations? So for example $a \equiv i$ mod $x$, $a \equiv j$ mod $y$ for some given $i,j,x,y$ with $gcd(x,y)=1$, and I must find $a$ mod $x*y$. Any tips on how to do this? ...
2
votes
1answer
47 views

Adding mod Values

I have the expression $$\frac{1000}{2^k} - \frac{n \pmod{2^k} + (1000-n) \pmod{2^k}}{2^k}$$ I know that the value of the expression is an integer, and I suspect that it is $$\frac{1000 - \ell \cdot ...
0
votes
1answer
55 views

Example for $a^k\equiv b^k$ and $k\equiv j$ but $a^j\not\equiv b^j\pmod n$

I need some help in the number theory please , Who can give me an example : If $$a^k≡b^k \pmod{n}$$ and $$k≡j \pmod{n}$$ is not necessary to be $$a^j≡b^j \pmod{n}$$
0
votes
1answer
54 views

$a^2\equiv1 \pmod n$ iff $a\equiv\pm\,1\pmod p$ for all $p\mid n$

(Not)if $a$ is an integer and $n$ a postive integer, then $a\equiv\pm 1\pmod p$ for all primes dividing n if and only if $$a^2\equiv 1\pmod n$$ $\Longrightarrow $ is wrong,Tonyk note ...
9
votes
1answer
84 views

Solving a Diophantine equation: $p^n+144=m^2$

I found this Diophantine equation: $$p^n+144=m^2$$ where $m$ and $n$ are integers and $p$ is a prime number. I solved it but I want to know if there exist other proofs through the use of rules of ...
0
votes
0answers
33 views

Define the concept of square root (mod n)

So i was looking at some of the past papers of my module, the new module has different topics slightly.I was wondering how would you solve this since we didn't cover such topic this year Define the ...
2
votes
0answers
51 views

Are there Latin squares with no repeats on the diagonal not of the form 2y+x+1(mod n)?

I am looking for a certain kind of latin square (nxn). Rules: No repeats in any column or row (Definition of Latin Square) No repeats in any diagonal including others than the main diagonal. So ...
1
vote
1answer
18 views

prove a function is not one-to-one

Let us look at the field $\mathbb{F}_{p}=\{0,1,2,...,p-1\}$ for a prime number p. And let $f:\mathbb{F}_{p}\rightarrow \mathbb{F}_{p}$ be the function given by $f(n)=n^2 \space (mod \space p)$. How ...
1
vote
3answers
31 views

What is the following expression simplified to?

$$x \mod 1000 \mod 5$$ I would have thought that it was $x \mod 5000$ except that it doesn't hold true for $x = 5005$ since you'll get zero, but $5005 \mod 5000 = 5$.
0
votes
1answer
10 views

Solving a congruence with an invertible piece

If I have $$a \equiv bp^k \bmod p^e$$ for $0 \leq k \leq e$ with $a,p,k,e$ known. How do I solve for $b$ given that $b$ is invertible?
0
votes
2answers
43 views

Hensel’s Lemma Number Theory Confusion

I have been given an example, finding the solutions of the congruence $f(x) ≡ 0$ (mod $5^4$) for $f(x)=x^2+1$ This solution finds that for mod $5$ we have $x_0=2$ . So through the 'lifting' process, ...
2
votes
3answers
49 views

If $x^2\equiv a\pmod n$, then $(n-x)^2\equiv a\pmod n$

Given that $x$ is a solution to $x^{2}\equiv a \pmod n$, show that $y=n-x$ is also a solution. Please don't solve, just give me a hint.
5
votes
4answers
50 views

Find $n\bmod 8$ when $n\bmod 56=29$

A number when divided by $56$ gives the remainder $29$. If it is divided by $8$ then what will be the remainder? Sorry if this is a stupid question, but I'm studying to improve my math.
0
votes
1answer
22 views

Show that $n\bmod m$ is periodic $\forall n,m \in \mathbb{N}^+$

How can I show that $n\bmod m$ is periodic? If I have a simple example like $n\bmod6 \equiv a$ how can I show that this is periodic if e.g $f(n) = n\bmod6$?
0
votes
1answer
48 views

How can I calculate $d$ from this equation?

So how can I calculate $d$ from this equation : $17^d \mod 55 = 8 $ ? I am solving an RSA Encryption question and im confused on how the modula is formulated when transferring to the other side, and ...
4
votes
3answers
84 views

Find $55! \bmod 61$

I am asked to find the smallest positive $x$ such that $x \equiv 55! \pmod{61}$. This invokes Wilson's theorem where $(p-1)! \equiv -1 \pmod p$. This means $60! \equiv -1 \pmod{61}$. But where to ...
1
vote
0answers
51 views

Solving the GCD m = 735, n =252

I understand everything except the values in $s_i$ and $t_i$ how do we get those values??? Can anyone please elaborate. I have no idea what the formula is for calculating the values in $s_i$ and ...
0
votes
2answers
91 views

Find 11^644 mod 645 [duplicate]

Can someone just explain to me the basic process of what is going on here? I understand everything until we start adding 1's then after that it all goes to hell. I just need some guidance. The Problem ...
2
votes
4answers
73 views

Prove if $7\mid a^2+b^2 \longrightarrow 7\mid a$ and $ 7\mid b$

Prove if $7\mid a^2+b^2 \longrightarrow 7\mid a$ and $7\mid b$ What I did: I found the possible remainders for $a^2$ are $0, 1, 2$ and $4$. I think I should say $r_7(a^2)+r_7(b^2)$ can't equal any ...
1
vote
2answers
33 views

Polynomial long division with mod. Trouble with fractions.

For example $4x^4 + x + 1$ divided by $3x + 1$ is $\frac{4x^3}{3} - \frac{4x^2}{9} + \frac{4x}{27} + \frac{23}{81}$ remainder $\frac{58}{81}$. Now I want to do the same division mod $9$, but I can't ...
1
vote
1answer
31 views

Repeating a Sequence

Initially I have provided x and y and the value of x and y repeatedly calculated until at some point the sequence is start repeating. ...
2
votes
2answers
64 views

Integer solutions of $ y^{2} = 5x^{2} + 17 $

Show that there are no integer solutions to the equation $$y^{2} = 5x^{2} + 17$$ using your knowledge of modular arithmetic and congruence classes. My attempt: Take 17 congruence mod 5 and show that ...
3
votes
2answers
92 views

Find three integers $x$ so that $271x \equiv 272\pmod{2015}$

I know that $\forall{a,n}\in\mathbb{Z}:\Bigl[\gcd(a,n)=1\Bigr]\implies\Bigl[\exists{k}\in\mathbb{Z}:ak\equiv1\pmod{n}\Bigr]$ In other words, for every pair of co-prime integers $a$ and $n$, there is ...
1
vote
1answer
28 views

Legendre Symbol $\left(\frac4p\right)$ is always congruent to $1$?

Let$\newcommand\leg[2]{\left(\frac{#1}{#2}\right)}$ $\leg ap$ denote the Legendre symbol. In all cases $a=4$. and $p$ takes values of different odd prime numbers $p$. For $p=5$: $\leg 45$ -> ...
0
votes
1answer
39 views

Generalized Fibonacci Sequence with Modular Arithmetic

Consider the following generalized Fibonacci sequence: Given $a$ and $b$ positive integers, and the known values $g_1, g_2, ...g_b$ where $g_k = g_k$ (mod $a$), then for ...
0
votes
0answers
31 views

Generalized Fibonacci Sequences G_{n+p}

I have been given the following generalized fibonacci sequences: For some positive integer $m,p$, $g_{n+p}=g_{n+p-1}+g_{n+p-2}+...+g_{n+1}+g_n (mod m)$ I have been given two problems: (1) For $m=2$ ...
0
votes
1answer
20 views

Unranking pseudo-random values to produce uniform distribution over all permutations

Following this question (and answers) on SO. The problem is to find a method to produce an unranking of combinatorial objects in random order, but in such a way that all possible orderings are ...
2
votes
2answers
40 views

Simple question about modular arithmetic

I am trying to understand if I could know something about the following relationship: If I have: $b \equiv n \mod a$ $d \equiv n \mod b$ $n \gt 0$ Is it possible to know something ...
0
votes
0answers
7 views

Finding quintuple of numbers with constrained size remainders

Given $A,B\in\Bbb Z_+$ of $(\frac{1}4+\epsilon)\log T$ bits, how could we find three numbers $P,Q,R\in\Bbb Z_+$ of atleast $\log_23 + \frac{1}4\log T$ bits such that in $$A = a_pP + m_p,\quad A = a_qQ ...
1
vote
0answers
29 views

What is the best known lower bound for: $\max_{2\leq i\leq p-1}(ord_n(i)) $?

Given an in integer $n$, and let $p$ be its smallest prime divisor (you can assume that $p$ is very large ). Let $ord_n(i)$ denotes the order of $i$ as an element of $\Bbb Z_n^*$ the multiplicative ...
1
vote
1answer
58 views

Trigonometric Functions And Modular Arithmetic

I was playing around on Wolfram Alpha and plugging in functions such as $$f(x)=2^{x}\bmod{x}$$ to see what some simple graphs might look like. Wolfram also returned some very interesting things such ...
1
vote
1answer
39 views

There exist arbitrarily long sequences of consecutive integers that are not square-free

Let $a$ and $n$ be positive integers. A sequence of $n$ consecutive integers $(a, a+1, a+2,...,a+(n-1))$ is called a Wolczuk of length $n$ if every integer in the sequence is divisible by some perfect ...
6
votes
1answer
110 views

The totient of Fibonacci numbers is divisible by $4$

Let $\{f_i\}_{i\in\mathbb N}$ be the sequence of Fibonacci numbers, i.e. $1,2,3,5,8,13,21,34,55,\cdots$, For every integer $n\gt3$ prove that $$4\mid\phi(f_n)$$ where $\phi$ is Euler's totient ...
4
votes
5answers
210 views

What is $2^{7!}\bmod{2987}$

Find the remainder when $2^{7!}$ is divided by $2987$. I tried to factorise $2987$ to make it simple but it was in vain.
0
votes
1answer
32 views

Calculate $\binom{n}{k}\pmod{10^6+3}$

I want to calculate the value of the following: $$\binom{n}{k}\pmod{10^6+3}$$ $10^6+3$ is prime if it may help. What is the math behind this? I can only understand basic modular arithmetic.
1
vote
1answer
36 views

Can modulo(remainder) be distribute over division?

Let $a\%b$ be the modulo operation, returning the remainder of $a$ when divided by $b$. Is it true that: $$\left(\frac{a}{b}\right)\% 5 = \frac{(a\% 5)}{(b\% 5)}$$ For instance, for $a=10$ and $b=2$ ...
1
vote
1answer
36 views

Is there any modular arithmetic property relating $\mod mn$ to $\mod m$?

We know that addition, subtraction and multiplication can be defined for integer modular arithmetic: for $a \equiv b \mod n$ and $c \equiv d \mod n$, $a+c \equiv b+d \mod n$ and so on. But is there ...