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
0answers
9 views

Let p be a prime number and let n ≥ 1. Show that $\mathbb{F}_p$ contains an element of order n iff p ≡ 1(mod n).

Let p be a prime number and let n ≥ 1. Show that $\mathbb{F}_p$ contains an element of order n iff p ≡ 1(mod n). For the reverse direction, assume $p \equiv 1(mod n). \text{Let } g \in \mathbb{F}_p ...
4
votes
2answers
25 views

$x^2$ $\equiv$ $1$ $\mod{p}$

Can someone provide the proof that $x^2$ $\equiv$ $1$ $\mod{p}$ iff $x\equiv1 \mod{p}$ or $x\equiv p-1 \mod{p}$, where $p$ is a prime? The argument I have in mind is setting up a bijection, like in ...
1
vote
1answer
40 views

Solve the following congruence for x (Modulo Question)

I need help in a question that I'm having a hard time understanding... It is asking to determine the congruence for $x$ and expressing the answer in the range 0-1000: $$ 200 . x = 13 \pmod{1001} $$ ...
0
votes
1answer
70 views

Is there any convention regarding the order of operation of the binary modulo operator?

Is there any predominant convention as to where the binary modulo operator (i.e., the variant of the modulo operator that is not applied to a whole equation) ranks in the order of operations, in ...
2
votes
3answers
49 views

Is modular arithmetic defined for all rational numbers (with denominators coprime to modulus)?

In the expression $\frac{1}{b}\pmod m$, where $(b,m)=1$, is $\frac{1}{b}$: a) a rational number (and so rational numbers are defined in modulo arithmetic using multiplicative inverses)? b) just ...
1
vote
0answers
27 views

Computation of large powers

How do I check if $2^{123456789}$ is divisible by 9? I tried using modular exponentiation but it is way too tedious. Is there an easier or faster way to solve it? Thanks!
1
vote
1answer
35 views

Primitive roots for a number

I want to show if a number a is a primitive root$\pmod{n}$ Is there a way to show this without raising a to all the powers between 1 and n-1?
1
vote
1answer
25 views

Internal and Direct Product question, need help with explanation

I am asked to express a group G={1,7,17,23,49,55,65,71} under multiplication modulo 96 as an external and internal direct product of cyclic groups. However I also have an example to help with it, but ...
2
votes
2answers
48 views

A question on divisibility

For what values of $x,y \in \{1,2,3,...9 \}$, does $$10x+y \space\mid 100x + y $$ ? What approach should I take for solving this problem ?
1
vote
0answers
27 views

Chinese Remainder Problem with three equations

Let's consider: $$*\begin{cases} 7x \equiv 2 \mod 5\\ 3x \equiv 2 \mod 4 \\ 5x \equiv 2 \mod 6 \end{cases}$$
1
vote
2answers
38 views

Principal Square Root mod

"Theorem: let p be a prime satisfying $p=3\bmod4$. Then for an integer y which is a square modulo p, $x=y^{(p+1)/4}\bmod p$ is a square root mod p of y. That is, $x^2=y\bmod p$. This is called the ...
0
votes
0answers
27 views

Strong pseudoprime base b

Show that the composite number 1281 is a strong pseudoprime base 41. "$n-1=2^rm$, then n is a strong pseudoprime base b if either $b^m=1modn$ or $b^{2^sm}=-1modn$" Ok so I have $n=1281$ and $b=41$ ...
0
votes
3answers
32 views

Modular equations: where did I make a mistake?

I want to solve the simultaneous congruences $$\begin{cases} 2x \equiv 4 \mod 8 \\ x \equiv 2 \mod 6 \end{cases} $$ My solution: $$2x \equiv 4 \mod 8 \iff x = 4l + 2 $$ $$x \equiv 2 \mod 6 \iff 4l + ...
0
votes
4answers
38 views

Modular arithmetic, very simple implications.

$$3t \equiv 1 \mod 4 \Rightarrow t \equiv 3 \mod 4 $$ I don't understand that, so I'm asking for explain me. Thank, in advance, greetings.
0
votes
3answers
35 views

Finding divisibility of a number using modular arithmetic

Let N = 12345678910111213141516171819. How can I use modular arithmetic to show that N is (or isn't) divisible by 11? In general, how can I apply modular arithmetic to determine the divisibility of an ...
0
votes
2answers
23 views

Question about modular arithmetic notation

In this document: http://cims.nyu.edu/~kiryl/teaching/aa/les092603.pdf The ordered pair notation is used but it is never explained what it means. ex: ...
0
votes
1answer
48 views

Proof, that $a \equiv 1 \pmod{p}$

Let $n \in \mathbb{N}^{+} \smallsetminus \{{1}\}$ and $p = min\{p \in \mathbb{P} : p \mid n\}$. Also, let $a \in \mathbb{Z}$ and $a^n \equiv 1 \pmod{n}$ I need to proof, that $a \equiv 1 \pmod{p}$. ...
0
votes
1answer
49 views

How to show a number is not a sum of squares

I've been tasked with the following: Let $m$ and $n$ be positive integers, prove that $4^{n}(8m+7)$ cannot be written as the sum of three squares. I've already gotten the idea that I should do ...
1
vote
1answer
36 views

Modular arithmetic and using in well-ordering principle

I need to prove the following, but I do not know how to go about it. If $$ (*)\:\:\: x^{3} - y^{3}= 3^{n} $$ Then $$ x \equiv 0 (mod 3) \:\: and \:\:\: y \equiv 0 (mod 3)$$ In addition, ...
-1
votes
2answers
61 views

Units in the ring $\mathbb{Z}(\omega)$

If $\omega \not= 1$ is a cube root of unity in $\mathbb{C}$, show that the units in the ring $\mathbb{Z}[\omega]$ are the elements of modulus 1. Hence, or otherwise, show that $U(\mathbb{Z}[\omega]$ ...
2
votes
1answer
36 views

computing $29^{25}$ (mod 11)

I'm trying to learn how to use Fermat's Little Theorem. $29=2\cdot11+7 \Rightarrow 11\nmid29$ by the theorem we have $29^{10}\equiv 1$(mod 11) $25=10\cdot 2 + 5$ $ ...
0
votes
1answer
17 views

Calculating nCr mod M using inverse multiplicative factors

The method used for calculating nCr mod M is: fact[n] = n * fact[n-1] % M ifact[n] = modular_inverse(n) * ifact[n-1] % M And then nCr is calculated as ...
2
votes
0answers
40 views

Compute digits of a number.

The question is what the last $10$ decimal digits of $2^{3^{4^{5^{6^{7^{8^9}}}}}}$ are? I do not get the following solution and its motivation. I would appreciate if someone would shed light on it. ...
0
votes
0answers
14 views

Pari/ GP Mod function

I am fairly new to using Pari/GP. Trying to compute below formula: y1=Mod((g^a1)*(y^a2),p); When I try to output y1, instead of giving me the value of Mod ...
4
votes
1answer
68 views

Congruence for the sums of odd powers of integers [duplicate]

Does someone know how to prove ***EDIT by induction**** that for all integers $n\ge1$, $k\gt0$ $$\sum\limits_{i=1}^{n} {i^{2k+1}}\equiv 0\ \ \ \pmod{\frac{n(n+1)}{2}}$$ I thought this should be a ...
0
votes
2answers
29 views

Prove divisibility

We have the following proposition: $$P(n): 13^n+7^n-2\vdots 6$$. Prove $P(n)$ in two ways. I know that one of them is mathematical induction. I don't know many things about the other one, I know ...
0
votes
2answers
18 views

Inverse of $3$ in $\mathbb{Z}_7$ using Fermat's Theorem or its corollaries.

What is $3^{-1}$ , the multiplicative inverse of $3$ in $\mathbb{Z}_7$. Use Fermat's Theorem or its collaries. How do I make use of the Fermat's theorem to solve this? I know how to solve it using ...
0
votes
0answers
15 views

Find $R[r] \mod M $ where R is a recurrence relation and M can be any integer?

Let N,M are two constant integers and they may or not be prime . A recurrence relation R is defined as using N $R[1]=1$ , $R[r]=\frac{R[r-1]\space * \space p}{r^r}$ , where $p = {(N-r+1)}^{(N-r+1)}$ ...
2
votes
3answers
69 views

Given that a and b are integers, a ≡ 4 (mod 13), and b ≡ 9 (mod 13). Find c where c ≡ 9a (mod 13).

The Problem I had my first exposure to number theory today. Trying to work on some problems in hope that it will start to make more sense. Here is the problem (part a) I'm stuck on right now. My ...
7
votes
0answers
58 views

Remainders of Fibonacci numbers

Let $a>b$ be positive integers. Is there a Fibonacci number that is $b$ modulo $a$? We know that the Fibonacci numbers are periodic modulo $a$. Indeed, consider pairs $(F_i,F_{i+1})$ modulo $a$. ...
1
vote
1answer
41 views

Breaking RSA Ciphertext

Sam and Tim have set up their RSA keys $(e_s, n), (e_t, n),$ respectively, where the n-value is the same. Furthermore, it happens that $\gcd (e_s, e_t) = 1$. Suppose that their friend Rob wants to ...
1
vote
1answer
49 views

Relation between $(a\bmod b)\bmod c$ and $a\bmod c$

Will (a%b)%c be equivalent to a%c? Given $b>c$ and $b$ is a prime number? If not is there any other equality that will hold? ...
0
votes
1answer
34 views

How to find $a\mod N $ in a specific way?

Let's I have an integer a and take it's modulo with M (M is a prime Number) which is b. i.e. $b = {a\mod M}$I would like to get $a \mod N$ by doing some operation on operation on b along with M , ...
0
votes
1answer
10 views

How do you create an operation for circular indices of a vector?

So I am trying to construct a way to find the next X letters (using the ASCII codes). But it is circular such that the next letter after Z is A. So Z+1 would be A. So basically it is an array (or ...
0
votes
2answers
27 views

Operations on congruence equations?

I have to do back substitution for my homework, and I have to modify x ≡ 1 (mod 5) to x=5t+1, which I understand. What I don't understand is when I put this into the next equation which becomes 5t + 1 ...
1
vote
1answer
140 views

question about cryptography

Sam and Tim have set up their RSA keys (eS; n); (eT; n), respectively, where the n-value is the same. Furthermore, it happens that gcd(eS;eT) = 1. Suppose that their friend Rob wants to send both Sam ...
0
votes
1answer
31 views

Euclid's proof for infinitely many prime numbers

Prove that there are infinitely many primes congruent to 3mod4 using euclid's proof for infinitely many prime number. I guess I don't really know where to start because I don't understand euclid's ...
1
vote
1answer
24 views

How do you compute $\frac{p}{qrs} \mod M$?

I would like to find $\frac{p}{q\space \space\space r\space \space s} \mod M $ . As multiplication of denominator can become large .So , $\frac{p}{q\space \space\space r\space \space s} \mod M $ = ...
2
votes
1answer
38 views

How to deal with negative exponents in modular arithmetic?

So I think I understand how to calculate something like $(208\cdot 2^{-1})\mod 421$ using extended euclidean algorithm. But how would you calculate something like $(208\cdot2^{-21})\mod 421$? ...
0
votes
1answer
21 views

Modular Division For non co-prime numbers

How can I calculate $(x*k)/i$ (mod $m$) where i and m are relatively not co-prime ? We know that, if $\gcd(i,m)\neq1$ , then there doesn't exist a modular multiplicative inverse of $i$ mod $m$. Then ...
0
votes
2answers
55 views

Fun results from modular arithmetic

I'm trying to go through various bits of neat, fun math with some junior-high-school students in my local area, and am thinking of doing a short unit on modular arithmetic/finite groups. I'm looking ...
0
votes
1answer
27 views

How to compute n(mod c) when n(mod a),n(mod b),a,b,c are given?

Given a(prime) > b (prime) > c(any number), is there any way to compute n(mod c) ? n%a,n%b,a,b,c are known.
0
votes
2answers
53 views

Show there is no solution to this equation

I have to show that $2x^4-20x+8$ cannot be divided by $16$ without remainder. The only thing comes to my mind is to write $16$ as $4^2$ which hasn't been of any help. Could you give me some hints to ...
0
votes
0answers
39 views

Finding value of given function with mod M

I want to calculate value of $F(N) = (F(N-1) * (N-R+1)^{(N-R+1)}/R^R)$ % M for given values of N,R and M. Here M need not to be prime. How to approach this question? Please help because if M was ...
1
vote
6answers
738 views

simple 'why' question about modular arithmetic 13 mod 5

After checking out khan academy "what is modular arithmetic" https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic they say that 13/5 = 2 ...
0
votes
1answer
33 views

Euclidean Algorithm / arithmetic mod question

I'm not sure how to approach this problem: Solve for $x$. $788x \equiv 24 (mod 1647)$. I know that if 24 were replaced with 1, I could just do a backwards euclidean algorithm to find x. Can I still ...
0
votes
2answers
35 views

What steps are needed to solve $5x+80 = 13 \pmod 7$ and similar problems?

I am unsure of the steps needed to solve $$5x+80 = 13 \pmod 7$$ or this, $$31x=2\pmod{19}$$ I would like to see the steps necessary.
-1
votes
1answer
23 views

Hexadecimal vs. Mod 16

Why is it that hexadecimal has both F and 0 when F is the 16th character in the sequence? Why is the same true of decimal notation? Doesn't this mean it is not compatible with modular arithmetic ...
0
votes
0answers
17 views

addition modulus n

I wan't to try and show (just for the sake of practice), why $$ a +_n a +_n a = (a + a + a) \mod{n} $$ I'm not really sure if I am going in the right direction with this, and would love a bit of ...
3
votes
2answers
15 views

Congruence equation for modulus 2

Suppose $a,b\in\mathbb{Z}$ and $n\in \mathbb{N}$. Is the equation $$((a+n)(b+n)) mod_2 = ((a-n)(b-n)) mod_2$$ satisfied? This is not a homework or such. (I'm not a student) I need to decide if two ...