Tagged Questions

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$.

2answers
288 views

Periodicity in strings

It is known that a string $s$ is actually made up of repetitions of another string $s_1$ of length $L_1$. Also $s$ can be thought of as made up of repetitions of another string $s_2$ of length $L_2$....
3answers
136 views

If $n$ is an integer then $\gcd(2n+3,3n-2)=1\text{ or ?}$

There are two possible Gcd's for integers of the form, $2n+3$ and $3n-2$ I know the gcd is $1$ if I take the equation modulo $2$. However if I take the equation modulo $3$ I get, $2n$ and $-2$. ...
2answers
65 views

How is this a field?

From Stephen Abbott's - understanding analysis there is a section in the text which says: "The finite set $\{0,1,2,3,4\}$ is a field when addition and multiplication are computed modulo 5." I wasn'...
2answers
134 views
+50

0answers
13 views

$i \equiv k \mod p \implies i = k$ if $p$ is prime?

In a particular proof of Fermat's Little Theorem $\big(a^{p} \equiv a \mod p \big)$ in Engel, the following fact is used $i \equiv k \mod p \implies i = k \:$ where $p$ is a prime. I'm not really sure ...
9answers
146 views

Last digit on $3^{100}$ [duplicate]

How to find the last digit on $3^{100}$? Is there any proper method to solve such questions without calculator of course?
8answers
191 views

Showing that $2^6$ divides $3^{2264}-3^{104}$

Show that $3^{2264}-3^{104}$ is divisible by $2^6$. My attempt: Let $n=2263$. Since $a^{\phi(n)}\equiv 1 \pmod n$ and $$\phi(n)=(31-1)(73-1)=2264 -104$$ we conclude that $3^{2264}-3^{104}$ is ...
1answer
41 views

What does ''$p$ of order $10\mod 11$'' mean?

What does ''$p$ of order $10\mod 11$'' mean ? $p$ is a prime, what are then the possibilities for $p$ ?
2answers
34 views

Why does an even $x$ imply $y^2=-2 \pmod 8$

I am very new to modular arithmetic, and I encountered the following statement on page 7 of this paper: If $x$ is even then $y^2 \equiv-2\pmod{8}$ The equation in question is $y^2=x^3-2$ I do not ...
1answer
38 views

Number of distinct remainders modulo n smaller than Euler's totient function

How come that the number of distinct remainders $a_{k}$ for $g^{k}\equiv a_{k} \mod (n)$ for specific positive $n$ and any positive $g$ and $k=1,2,3...$ is never greater than $\varphi (n)$ (Euler's ...
1answer
29 views

If I know N%m , can I compute (N/2)%m? If yes, then how?

This question arrised when I was solving a computer science problem. I don't know the value of N, as N may be very large, but instead I know the value of $N \mod m$. Assume N is divisible by 2. How ...
1answer
39 views

Show that if two integers are in this relation then so are their powers

$a\sim b$ is defined as $m$ divides $b-a$, where $m$ is some fixed arbitrary positive integer. Assume $A\sim a$. Show $A^n\sim a^n$ for every positive integer $n$.
0answers
49 views

Is there an nth term for this system of modular Equations?

I am interested in the 1st solutions to this set of equations, and wonder if there are any techniques I could use to try and yield an nth term. I'll provide the first few for clarity. General ...
1answer
442 views

Conjecture about primes and the factorial: for all primes $p>5$, must there exist a prime $q<p$ such that $q\equiv m!\pmod p$ for some $2<m<p$?

Below $0\notin\mathbb N$. Further corrected conjecture: For all prime numbers $p>5$ there exist a prime number $q<p$ such that $q\equiv m!\!\pmod p$, $2<m<p$. or Given a prime ...
2answers
49 views

Prove or disprove that $(A\mathbin\%B)\mathbin\%C = (A\mathbin\%C)\mathbin\%B$ [on hold]

Prove or disprove that $(A\mathbin\%B)\mathbin\%C = (A\mathbin\%C)\mathbin\%B$ I am not able how to prove (or disprove by example ) that $(A\mathbin\%B)\mathbin\%C = (A\mathbin\%C)\mathbin\%B$? ...
6answers
91 views

Remainder when $5^{5555}$ is divided by $10000$. [duplicate]

Find the remainder when $5^{5555}$ is divided by $10000$. A step by step guide with explanation for a beginner student in modular arithmetic is needed.
2answers
69 views

Solve for $b$ in $2^b\bmod11=7$

If I have the equation- $$2^b \bmod 11 = 7$$ How can I solve this to find out what $b$ is? I know $b$ is $7$ but I'd like to know how this is done mathematically rather than guessing.
1answer
52 views

How to prove that $\lfloor \frac{n}{2}\rfloor$ = $\lceil \frac{n-1}{2}\rceil$

I'm having a hard time proving that: $$\left \lfloor \frac{n}{2}\right\rfloor = \left\lceil \frac{n-1}{2}\right\rceil$$ I've tried various algebraic manipulations. I've also tried to see if I could ...
3answers
38 views

$(a^2) \equiv 1 \pmod{k}$ - we are looking for $a$ - fast way

We have the equation: $(a^2) \equiv 1 \pmod{k}$ We know $k$. It is a quick way to find $a$? (of course other than $1$)
5answers
2k views

How do I subtract times?

I have an embarrassingly basic modular arithmetic question. I understand that I can subtract, for example, 1 hour from 10 o'clock to get 9 o'clock, or even 2 hours from 1 o'clock to get 11 o'clock; ...
0answers
138 views

Are all theorems usable? [closed]

The (revised) question to answer: Can anyone give an example of a serious proof using this funny (revised) theorem? For any natural number $n$ and prime $p<n-1$ there exist a prime $q$ ...
1answer
45 views

Simpler way to compress this exponentiation?

I am trying to find when the following is true: Let $H =(10k)^b \bmod 6(p-1)$ Let $J = 10^{H} \bmod 9p$ For some prime $p > 5$ and large $k,b$. I am trying to find when $J$ is equal to $1$. ...
0answers
20 views

Solving a system of congruences with unkown moduli?

So I have two congruences of the form: n[1]=r[1] mod m and n[2]=r[2] mod (a*m+b) with known n,r,a, and b. Is there a way way to efficiently get (an acceptable) m? Edit: I mean is there any way ...
1answer
47 views

How to prove equivalencies for any n? [closed]

The specific problem im trying to solve is the following: $441n^{43} + 374n^{35} + 283n^{23} = 0$ mod $55$ is true for all $n$ but im not sure how to prove that. Any leads on how to start would be ...
1answer
18 views

Construct a function pertaining to the OEIS sequence A131229 (Numbers congruent to {1,7} mod 10)

OEIS sequence A131229 ("Numbers congruent to {1,7} mod 10") begins $\{1, 7, 11, 17, 21, 27, 31, 37, 41, 47, 51,...\}$. I want a function $f(x)$, specifically such that $f(\frac{1}{2}) =\frac{7}{2}$, ...
2answers
22 views

1answer
26 views

If $d\mid n$, element of $(\mathbb{Z}/n\mathbb{Z})^*$ of highest order is also element of $(\mathbb{Z}/d\mathbb{Z})^*$ of highest order

I am not entirely sure if the following lemma is true, but after running a code to check, for smaller values of $n$, it holds. Can someone outline the proof or give a counterexample for it. Lemma: ...