1
vote
2answers
56 views

Compute $F_{1000} \bmod F_{11}$, where $F_n$ denote the Fibonacci numbers

Compute $F_{1000} \bmod F_{11}$, where $F_n$ denote the Fibonacci numbers. Progress: $F_{11}=89$ . I believe you should find the period of $F_n \bmod 89$ and use that to solve it. But I'm not not ...
-1
votes
1answer
34 views

$p>3$ prime, show that there exists $0<x,y<\sqrt{p}$ so that $p$ divides $cx-y$

Let $p>3$ be a prime number that does not divide $c$. Show that if $p>3$ there exists $x$ and $y$ with $0<x,y<\sqrt{p}$, such that p divides $cx-y$. I believe I've shown the above but for ...
0
votes
1answer
66 views

Find the largest integer $n$ such that $10^n$ divides $10^6!$

Let $N=10^6!$ Find the largest integer $n$ such that $10^n$ divides $N$. Furthermore, compute the first digit and the last non-zero digit of $N$. I have some ideas that you should be able to use ...
1
vote
1answer
64 views

Compute $F_{1000} \bmod 1001$, where $F_n$ denote the Fibonacci numbers

Compute $F_{1000} \bmod 1001$, where $F_n$ denote the Fibonacci numbers. I have tried using the fact that $F_{n^k} \bmod F_n = 0, k=1,2,3,...$ but that doesn't get me anywhere. Thanks!
1
vote
2answers
72 views

Solving $x^2 + 96=0$ in $\mathbb{Z}_{100}$

I'm trying to find all solutions to $x^2 + 96=0$ in $\mathbb{Z}_{100}$. $x^2 + 96 \equiv 0 \bmod 100$ implies that $x^2 + 96 \equiv 0 \bmod 2$ and $x^2 + 96 \equiv 0 \bmod 5$. $$x^2 + 96 \equiv 0 ...
1
vote
2answers
29 views

Discrete log modulo prime

I'm trying to understand properties of the discrete logarithm problem modulo a prime. For a prime $p$, an $\alpha \in \mathbb{Z}_p^*$ and $a \in \mathbb{Z}_{p-1}$ why does $\alpha^x \equiv 1 \mod p$ ...
1
vote
2answers
54 views

Show that there exists no integer coordinates on curve

Problem: Show that there does not exist any integer coordinates to the curve $$y = \frac{x^2-3}{4}, x\in \mathbb{R}.$$ My attempt: The problem is equivalent of saying that there does not exist any ...
0
votes
1answer
37 views

The addition table for $\mathbb Z/4$ - modular arithmetic

"Write down the addition table for $\mathbb Z/4$ " Could someone please give one or two hints? And what does them mean with $\mathbb Z/4$? They have never used that notation before. Do them just mean ...
1
vote
0answers
52 views

Solving the discrete logarithm using index calculus, finite fields and factor bases.

(a) Let $p$ be the prime 1073741827, with $\Bbb{F}_p$ the corresponding finite field. A primitive root in $\Bbb{F}_p$ is equal to $g=2$. Use a factor base of primes up to 13 to find the discrete ...
0
votes
1answer
24 views

Finding discrete maps with prescribed cycle-structure (functional digraph-structure)

I apologize in advance for the naive nature of the following questions. I am also thankful to suggestions for improving the direction of the questions instead of direct answers. Let $f: \mathbb N \to ...
-1
votes
3answers
51 views

mod of minus power 1

I am fully aware on how to perform mod calculation. The issue now is that when I have this $2^{-1} \bmod 10$. How to do this? Is there any formula for this?
4
votes
3answers
591 views

Prove that every prime larger than $3$ gives a remainder of $1$ or $5$ if divided by $6$

Can we prove that every prime larger than $3$ gives a remainder of $1$ or $5$ if divided by $6$ and if so, which formulas can be used while proving?
4
votes
0answers
32 views

Subsets of cyclic group with distinct pairwise differences

Given a number $m\in\mathbb N$, let $\mathbb Z_m=\{0,1,\dots,m-1\}$ denote the ring of integers modulo $m$ (although we won't need multiplication, so any cyclic group of order $m$ will do). Given a ...
0
votes
1answer
114 views

Solving mod congruence

So i have a problem like this 34x ≡ 77 (mod 89) This is how i try to solve it but it doesn't seem to work :( If anyone can give me a hint on how to proceed from ...
0
votes
3answers
65 views

Discrete mathematics. Just an impression, or this is always true?

I feel that the following is always true: $$ \frac{2^k-1}{3} \equiv 1 ~(\text{mod }2) \text{ if }k \equiv 0 ~(\text{mod }2) \wedge k \geq 2$$ I've just tried it using a "brute force" approach, but ...
1
vote
1answer
37 views

Proving modulo equation with x-power

I'm trying to prove following equation: $$ (g^{y} \mod n)^x \mod = g^{xy} \mod n $$ I tried many multiple approaches, all of them failed, and there is waaay too much of them to write them here, so I ...
0
votes
1answer
19 views

Calculate power of large numbers mathematically?

Is there a short-hand method to find the value of a number with a large power. For example : 1024^2048
0
votes
1answer
83 views

Convert modulo 65 into modulo 26.

Is there anyway to convert x ≡ 9 (mod 65) into x ≡ something (mod 26)? Generally is there a way to convet one modulo into some other modulo?
1
vote
1answer
44 views

Applying the Chinese remainder theorem

I am trying to apply the Chinese remainder theorem to obtain the unique solution modulo $10^n$ for $N\equiv 1 \pmod {2^n}$ and $N\equiv 0 \pmod {5^n}$. I have reason to suppose that the solution is ...
0
votes
2answers
47 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 ...
2
votes
0answers
38 views

Modular arithmetic - Suggestions to begin

I've always wanted to start studying modular arithmetic to try to solve problems like: $$\text{find } n \in \mathbb{N} : 4n^2 \equiv 1 ~(\text{mod }{10^4})$$ I have a good basis in mathematical ...
2
votes
1answer
55 views

Show that for all natural $a$, $2008\mid a^{251}-a$.

How to show, that for all natural $a$ coprime to 2008 the following occurs: $2008\mid a^{251}-a$? This means, that $a_{251} \equiv_{{}\bmod 2008} a$, right? It's obvious if $a\mid 2008$. In the ...
2
votes
2answers
134 views

Determine the smallest multiple of 9 which divided by each of the numbers 2, 5 and 11 leaves a remainder 1.

The question is: Determine the smallest multiple of 9 which divided by each of the numbers 2, 5 and 11 leaves a remainder 1. The answer is 441. What I did when I tried solving this was to set up 3 ...
0
votes
3answers
141 views

Book on modular arithmetic

I am searching for some good book which section is devoted to modular arithmetic. I am self learner so I strongly prefer that book has exercises best with answers or solutions. I have CS background ...
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 ...
4
votes
4answers
129 views

Solve $x^2+x+3=0$ mod $27$

I was preparing for my Number Theory class for next semester and one of the questions that I came upon is to solve $x^2+x+3=0$ mod $27$. I have seen modular arithmetic before but never one that ...
2
votes
2answers
76 views

Is the following always True?

Let $a, b \in Z$ and $n \in N$ . Is the following necessarily true? If $a^3 ≡b^3$(mod n) then $a ≡ b$ (mod n) How do I do this? For the record, I do not think this is True.
0
votes
3answers
440 views

Prove if $a \equiv c \pmod n$ and $b \equiv d \pmod n$ then $ab \equiv cd \pmod n$.

Prove if $a \equiv c \pmod n$ and $b \equiv d \pmod n$ then $ab \equiv cd pmod n$. I tried to use $(a-c)(b-d) = ab-ad-cb+cd$, but it seem doesn't work.
1
vote
1answer
74 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 ...
-1
votes
1answer
60 views

UPC code proof help

i'm trying to prove the following problem.. 1. Prove that if a single digit of a valid UPC is changed then the new code is not valid. Answer - When the question ...
0
votes
2answers
36 views

Congruence equation proof

Proof that $\forall{a}\in\Bbb N \rightarrow a^3\equiv a\mod (a+1)$ I do not know how to prove these equations. I only know that $a\equiv m \mod b \implies m | ( b- a ) \implies b-a=m\times k $ for ...
2
votes
3answers
35 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 ...
1
vote
1answer
24 views

Solving linear congruences

I am trying to solve $25x\equiv15\pmod{29}$ I multiply both sides by $7$ which makes the L.h.S congruent to $1x \pmod{29}$ From this I have that $7\times25x\equiv7\times15\pmod{29}$ I am really ...
0
votes
2answers
53 views

Modular Arithmatic

I have been struggling with modular arithmetic, and I would like to try and finally grasp the concept. In particular, solving problems like $7^{30}$ mod 49. I know I will have to use Fermat's Theorem ...
2
votes
1answer
63 views

Recursive Function - mod 5

How do the recursive function for $\mod 5(x) = 0$ rest of division of $x$ by $5$. $$\begin{align} \mod&5(5) = 0\\ \mod&5(6) = 1\\ \mod&5(7) = 2\\ \mod&5(8) = 3\\ \mod&5(9) = 4\\ ...
0
votes
1answer
117 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 ...
0
votes
1answer
44 views

The closed form of a sum of mod(k,m) where k goes from 1 to a arbitrary number.

Is there a closed form for $\sum_{n=0}^{C} mod(n,m)$ for arbitrary integers m ?
2
votes
1answer
69 views

Proof related with prime numbers and congruence

How to (dis)prove this $ (n-2)! \equiv 1 \mod n$ If n is said to be a prime number. I guess we'll have to use FERMAT’S LITTLE THEOREM, and I just don't know where to start from. Thanks in advance ...
1
vote
1answer
56 views

Proofs related with odd numbers and modulo 8

In my problem I have $ s! + s^{2P} \equiv 1 \mod 8$ where $s > 4, P \geq 1, s,P \in \mathbb{Z}^+$ I tried to follow that example's logic, but I could not get a result $n^2 \equiv 1 \mod 8$ ...
-1
votes
1answer
66 views

prime number related proof

I want to prove if following is true for every integer a,b and c $$a^2 - b^2 = cp $$ then p|(a+b) or p|(a-b) where p is a prime number. Any suggestion, help would be highly appreciated. Thanks ...
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
29 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
81 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
1answer
86 views

Modular arithmetic and one-to-one functions

Let $S = \{0, 1, 2, 3, · · · , 99\}$ . For each of the following functions $f : S \rightarrow S$ , determine whether it is one-to-one and onto, by computing its values for all $k ∈ S$: Function 1: ...
18
votes
4answers
1k views

Is the number $333, 333, 333, 333, 333, 333, 333, 333, 334$ a perfect square?

I know that if the number is a perfect square then it will be congruent to 0 or 1 (mod 4). Now since the number is even, I know that it is either 0 or 2 (mod 4). How would I go about answering this? ...
0
votes
2answers
45 views

Prove that for every $x \in \mathbb{Z}$ for which $x \geq 3$, if $x \equiv 3 \pmod 4$ then $3^x - 2 \equiv 0 \pmod 5$

Prove that for every $x \in \mathbb{Z} \geq 3$, if $x \equiv 3 \pmod 4$ then $3^x -2 \equiv 0 \pmod 5$. I was trying to use induction: Base case $(x = 3)$: If $3 \equiv 3 \pmod 4$ then $3^3 - 2 ...
1
vote
1answer
33 views

How come when $2^{k} | (x-1)(x+1)$ one of the terms is divisible by $2$ and not by $4$ when $k \in \mathbb{N} $ and $3 \leq k$

So I'm reading Knuth's 'Discrete Mathematics' at the moment and there's a paragraph detailing how many solutions are there for $x^{2} \equiv 1 \pmod{p}$. So other cases (when $p$ is an odd prime or ...
0
votes
1answer
37 views

Question about $a \equiv b \pmod{mn} \Leftrightarrow a \equiv b \pmod{m} \wedge a \equiv b \pmod{n}$

So Knuth's 'Discrete Mathematics' states that: $a \equiv b \pmod{mn} \Leftrightarrow a \equiv b \pmod{m} \wedge a \equiv b \pmod{n}$ if $m$ and $n$ are relatively prime. But being a curious human ...
4
votes
2answers
62 views

Smallest such $n \in \mathbb{N}$ that $2^{n} \equiv 1 \pmod{5\cdot 7\cdot 9\cdot 11\cdot 13}$

Can anybody give me a hint about how to find smallest such $n \in \mathbb{N}$ that $2^{n} \equiv 1 \pmod{5\cdot 7\cdot 9\cdot 11\cdot 13}$? I thought that I will find it piece by piece with help ...
0
votes
0answers
46 views

Must the “n” in mod(n) always be prime?

I'm experimenting with mod(n) and have the following questions even after reading the Wiki page and numerous articles about the subject. Must mod(n) always be prime for cryptographic purposes? Is ...