Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms (1)

1
vote
0answers
151 views

Find the lowest common divisor greater than N?

For a given set of numbers, I need to find the lowest common divisor that's higher than a given number, N. Is there a way to do that?
1
vote
0answers
52 views

Algorithms for Performing Large Integer Matrix Operations w/ Numerical Stability

I'm looking for a library that performs matrix operations on large sparse matrices w/o sacrificing numerical stability. Matrices will be 1000+ by 1000+ and values of the matrix will be between 0 and ...
0
votes
2answers
166 views

Find the congruence of $4^{578} \pmod 7$

Find the congruence of $4^{578} \pmod 7$. Can anyone calculate the congruence without using computer? Thank you!
0
votes
1answer
423 views

Determining the existence of an integral linear combination

Given $x, y, r \in \mathbb{Z}$, how can you tell whether there exist two integers $a$ and $b$ such that $ax + by = r$? That is, how do you determine whether an integral linear combination exists for ...
1
vote
2answers
158 views

Roots of unity in $\mathbb{C}$ sum of roots

I want to know why if $F(n)$ denote the sum of the primitive $n$th roots of unity in $\mathbb{C}$, and $G(n)$ denote the sum of all complex $n$th roots of unity. Then $G(n)=\sum_{m|n}F(m)$, Please, I ...
1
vote
1answer
124 views

What about the Cauchy-Frobenius-orbit-counting formula

I know the proposition that says: Let $\lambda$ be a homomorphism from a finite group $G$ into $\mathbb{C}^{\times}$. Suppose that $G$ acts on some finite set $\Omega$ and let $M$ be the number of ...
6
votes
1answer
252 views

Seeking a proof of $\sum_{d|n}\phi(\frac{n}{d})a^d\equiv 0 \mod{n}$, where $\phi$ is the Euler Totient Function.

I need to prove the proposition. Let $a$ be an arbitrary integer. Then for every positive integer $n$, we have $$\sum_{d \mid n}\phi\left(\frac{n}{d}\right)a^d\equiv0\pmod{n}.$$
5
votes
2answers
396 views

Roots of unity and function $\mu$

I need to prove that for each positive integer $n$ the sum of the primitive $n$th roots of unity in $\mathbb{C}$ is $\mu(n)$, where $\mu$ is the Möbius function.
4
votes
3answers
189 views

A question about Fermat numbers

This is a question in a book in Portuguese. Let $p_n$ be the $n$-th prime number. Show that $p_n\leq 2^{2^{n-2}}+1$. The book gives a hint: use the facts that $\gcd(F_i,F_j)=1$, if $i\neq j$, ...
0
votes
2answers
110 views

Sylvester Theorem

Bonjour, The equation $\binom{n}{k}=m^l$ has no entire solution for l$\ge$2 and 4$\le$k$\le$n-4. Suppose that n$\ge$2k (since $\binom{n}{k}=\binom{n}{n-k}$). According to the Sylvester theorem, the ...
3
votes
1answer
114 views

$x^2 \equiv 2x \pmod m$

Toward counting the solutions for the congruence $x^2 \equiv 2x \pmod n$, if we write $m$ as $m = p_1^{a_1}p_2^{a_2}...p_r^{a_r}$ we have the following equivalent system of congruence equations: ...
2
votes
0answers
137 views

For which positive integers n does there exist a prime whose digits sum to n?

Motivated by this earlier question, I thought of this problem: Question: For which positive integers $n$ does there exist a prime whose decimal digits sum to $n$? We can make two "easy" ...
1
vote
0answers
64 views

Proof of a Continued Fraction Identity using basic CF definition.

Two definitions (the first is informal) of continued fraction: This is the basic Continued Fraction algorithm for real numbers. Let $\alpha \in \mathbb{R}$. If $[\alpha]=\alpha$, then we are done. ...
1
vote
3answers
209 views

Number Theory Problem $ax+by=n$ for $n>ab$

Let $a,b \in \Bbb N$ with $\gcd(a,b)=1$. Show that for every integer $n>ab$ the equation $ax+by=n$ has a solution in positive integers $x,y$. (Take $(x,y)$ with $y \leq 0$ and $x$ minimal).
0
votes
1answer
230 views

Euler's Criterion and Wilsons Theorem

I am trying to prove: if $m = p_1p_2\cdots p_r$ with $2 < p_1 < \cdots < p_r$ prime, then $$x^2 \equiv 1\mod m$$ has $2^r$ solutions modulo $m$. I know Euler's Criterion: $p$ is an odd ...
0
votes
4answers
296 views

Solutions of the equation $ax+by=ab$

Let $a,b \in \Bbb N $ with $\gcd(a,b)=1$. The equation $ax + by = ab$ has the obvious solution $(b, 0)$ in integers. Show, however, that it has no solution in positive integers.
2
votes
1answer
71 views

Probability Factorization Algorithm

I want to prove the following: Let $n = pq$, with $p, q$ distinct odd primes. Let $x,y$ be random integers with $\gcd(xy, n) = 1$ and $x^2 \equiv y^2 \mod n$. Prove that there is a 50-50 chance that ...
0
votes
1answer
51 views

orders of elements and multiplicative inverse module m [duplicate]

Possible Duplicate: Find $ord_m b^2$ if $ord_m a = 10$ and $ab\equiv 1\pmod m$ If $ab \equiv 1 \pmod{m}$ and if $ord_ma=10$, find $ord_mb^{2}$. I know that $ab \equiv 1 \pmod{m}$ is used ...
0
votes
2answers
58 views

Use $\operatorname{ord}_{11}3$ to find remainder when..

Find $\operatorname{ord}_{11}3$. Then use what you found to find the remainder when you divide $3^{82}$ by $11$. Work thus far: $$\operatorname{ord}_{11}3=\ ?$$ $$3^1\equiv3\pmod{11}$$ ...
0
votes
1answer
1k views

Proving that floor(n/2)=n/2 if n is an even integer and floor(n/2)=(n-1)/2 if n is an odd integer.

How would one go about proving the following. Any ideas as to where to start? For any integer n, the floor of n/2 equals n/2 if n is even and (n-1)/2 if n is odd. Summarize: ...
0
votes
6answers
313 views

How to multiply decimal with wholenumber?

How Can I multiply x = (0.35)(80) x = 28 steps by step fastest way I am not going to lie, but it is time for me to take a test without using a calculator. Schools have made me worse by giving us a ...
1
vote
1answer
63 views

For any number $n \gt 1$ and all of its prime divisor $d_1, d_2, …$ s.t. $d_i \equiv 1 \pmod 3$ for each $i$, show:

For any number $n \gt 1$ and all of its prime divisors $d_1, d_2, ...$ s.t. $d_i \equiv 1 \pmod 3$ for each $i$ Show that the euler phi function $\phi(x) = 2n$ has no natural number solution.
3
votes
1answer
132 views

The set $A = \{a^2 + 2b^2\mid a,b \in \Bbb Z\setminus\{0\}\}$

Let $A = \{a^2 + 2b^2\mid a,b \in \Bbb Z\setminus\{0\}\}$ and $p$ be a prime number. Prove that if $p^2 \in\ A$, then $p \in A$.
10
votes
2answers
256 views

If $\dfrac{4x^2-1}{4x^2-y^2}$ is an integer, then it is $1$

The problem is the following: If $x$ and $y$ are integers such that $\dfrac{4x^2-1}{4x^2-y^2}=k$ is also an integer, does it implies that $k=1$? This equation is equivalent to ...
8
votes
2answers
284 views

Prove that for all non-negative integers $m,n$, $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is an integer.

Prove that for all non-negative integers $m,n$, $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is an integer. I'm not familiar to factorial and I don't have much idea, can someone show me how to prove this? ...
1
vote
0answers
83 views

Pollard $p-1$ factorization

I need some help understanding this algorithm. I want to factor $n$. Suppose $n$ has a factor $p$ s.t. the primes that divide $p-1$ are less than $10,000$. And $p-1$ divides $10000!$. Let $m = ...
3
votes
1answer
506 views

Why there is this kind of relation between power and factorial?

What I am talking about is a fact, that if we write down n-th powers of consecutive natural numbers in a row, and then on the next row between each two numbers write their difference and repeat this ...
2
votes
2answers
46 views

Using the RSA system…

Using the RSA system with $(m,e)=(51,5)$ find a $d\ge1$ that will decode the messages. What I have so far (not sure if this is right): Since, $m=51$ and $e=5$ then the $\gcd(51,5)=1$ then: $$5d ...
1
vote
0answers
87 views

Understanding of Pollard rho factorization

I am trying to better understand the ideas and intuition behind the Pollard Rho factorization algorithms. Given an $x_0$ and an irreducibe polynomial we can create a sequence from the recursive ...
1
vote
4answers
116 views

Find $ord_m b^2$ if $ord_m a = 10$ and $ab\equiv 1\pmod m$

If $ab \equiv 1 \pmod {m}$ and if $ord_ma=10$, find $ord_mb^2$. Could somebody give me a hint? What I know is that $ab \equiv 1 \pmod {m}$ can be used when finding the multiplicative inverse. Would ...
0
votes
2answers
59 views

Give the remainder when..

Give the remainder when you divide $3*(16!)+2$ by $17$. I don't have much to go on, but i'm not asking you to simply give me the answer even though that would be great. Could someone show me where I ...
1
vote
0answers
54 views

Find the orders..

$\newcommand{\ord}{\operatorname{ord}}$ Find the orders below: \begin{align} & (a) \quad \ord_{11}5 \\ & (b) \quad \ord_{7}4 \\ & (c) \quad \ord_{23}22! \end{align} For the most part, I ...
0
votes
2answers
1k views

Find a multiplicative inverse…

Find a multiplicative inverse of $a=11$ modulo $m=13$. What is this saying? This seems like such a simple question, I just don't understand what it is asking for. An additional question related to ...
2
votes
2answers
321 views

Find all integer solutions to linear congruences

Find all integer solutions to linear congruences: \begin{align} &(a) &3x &\equiv 24 \pmod{6},\\ &(b) &10x &\equiv 18 \pmod{25},\\ \end{align} What I have so far: $$(a) ...
4
votes
4answers
3k views

How to prove gcd of consecutive Fibonacci numbers is 1? [duplicate]

Possible Duplicate: Prove that two any consecutive terms of Fibonacci sequence are relatively prime How to proof it ? Can you help me ? Let $f_n$ be Fibonacci Sequence. ...
1
vote
2answers
323 views

Could you give me some small research questions in the university level?

I want to do some study about math in the university level, but i have no idea about choosing problems. The fact is that i try to take part in a research activity from our school, but when i got the ...
0
votes
1answer
117 views

What is the biggest positive integer within 100 that can be/can not be written as the differences between two positive primes?

What is the biggest positive integer within 100 that can be/can not be written as the differences between two positive primes? Can someone answer the cannot part? There are two parts in the ...
0
votes
1answer
93 views

Show the number of solutions

Show that the number of solutions of $x^2+y^2=m$, where $m=2^{\alpha}r$ and $r$ is odd, is given by $U(m)=4\sum_{u|r}(-1)^{\frac{u-1}{2}}=4\gamma(m)$, where $\gamma(m)$ denotes the number of positive ...
3
votes
3answers
365 views

Show $m^p+n^p\equiv 0 \mod p$ implies $m^p+n^p\equiv 0 \mod p^2$

Let $p$ an odd prime. Show that $m^p+n^p\equiv 0 \pmod p$ implies $m^p+n^p\equiv 0 \pmod{p^2}$.
1
vote
0answers
71 views

How difficult is to find x for x^2 mod N = a, where a = 1?

Is it any easier to find $X$ for $a=1$ than some other $a$'s that is smaller than $N$. $a$ is quadratic residue.
1
vote
1answer
645 views

How to solve multiplication alphametics?

I am referring to puzzles like these, where every letter represents a unique number (0-9): ...
1
vote
2answers
3k views

How to solve this alphametic (verbal arithmetic)?

I know I can get the answer for this puzzle but I'm struggling to see how to solve it. Every letter represents a different number (0-9): ...
0
votes
1answer
102 views

Topic discussed in number theory today.

Showing $\mathrm{ord}_d(a) \mid \mathrm{ord}_m(a)$ if $d \mid m$. Also, let $1\le d$, $1 \le m$, and $\gcd(a,d)=1$. What I have so far is: Let $x=\mathrm{ord}_m(a)$. Then we have $a^x\equiv 1 ...
1
vote
1answer
98 views

How can I proceed in proving number theory/set exercise?

The problem states: Prove that: In every set of 100 integers, there exists two distinct integers x and y s.t. 89 | (x-y) So far the only thing I've determined is that 89 is prime, so 89 | (x-y) if ...
0
votes
1answer
379 views

Peano's Postulates Proofs

How can I prove the following two questions: Prove using Peano's Postulates for the Natural Numbers that if a and b are two natural numbers such that a + b = a, then b must be 0? Prove using Peano's ...
0
votes
3answers
307 views

How to prove that some number has a particular factor without dividing

Suppose that there is a natural number. One wants to show that the number has particular (natural number) factor, but without dividing the number by the "supposedly" factor. How does one do this?
7
votes
2answers
633 views

Number of permutations which fixes a certain number of point

Given the set $N:=\{1,\cdots,n\}$, let $\pi$ be a permutation on $N$. We say $i \in \{1,\cdots,n\}$ is fixed by $g$ iff $\pi(i)=i.$ Denote the set of all permuations on $N$ by $S_n$. Define $f :~N ...
0
votes
2answers
139 views

Show that $\mathrm{ord}_m(a)=\mathrm{ord}_m(b)$ if… [closed]

Let $\gcd(a,m)=1$ for some $m\ge1$. Then we know that $a$ has a multiplicative inverse modulo $m$. Let $b$ be such an inverse. Argue that $\mathrm{ord}_m(a)=\mathrm{ord}_m(b)$.
2
votes
2answers
68 views

Showing $\operatorname{ord}_ma^s=k$ if $\gcd(s,k) = 1$ and $\operatorname{ord}_ma=k$

If $\operatorname{ord}_ma=k$ and if $\gcd(s,k)=1$ for some $s\ge1$, prove that $\operatorname{ord}_ma^s=k$. I know that $a^n\equiv 1 \pmod m$ for $n \ge 1$ if and only if $k\mid n$. However, I don't ...
0
votes
1answer
90 views

Why don't all elements of an arithmetic progression divide the lcm of the start and step?

I'm getting back into basic proofs after a long hiatus, and I know something has to be wrong with the following logic but I'm not sure what. Elements of arithmetic progressions can be expressed as: ...