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

learn more… | top users | synonyms (1)

1
vote
4answers
78 views

Find the sum to $n$ terms of the series $10+84+734+…$

Find the sum to n terms of the series $10+84+734+....$ $\frac{9(9^n+1)}{10} + 1$ $\frac{9(9^n-1)}{8} + 1 $ $\frac{9(9^n-1)}{8} + n $ $ \frac{9(9^n-1)}{8} + n^2$ My attempt: I'm getting option ...
1
vote
2answers
25 views

Cubic modular equation

If i found the sol of (a), i can find sol of (b) and (c) by using hensel's lemma i want to know the way of solving (a) without testing all the case (ex testing 1,2,3,4,...10) I think that there ...
1
vote
1answer
38 views

The exponent of $11$ in the prime factorization of $ 300!$ is___.

The exponent of $11$ in the prime factorization of $ 300!$ is $27$ $28$ $29$ $30$ My attempt: According to Exponent of $p$ in the prime factorization of $n!$ ...
1
vote
3answers
55 views

Is it true: $3k^2+1$ is a perfect square if and only if $k=1$ or $4$

I'm checking the following conjecture: $3k^2+1$ is a perfect square if and only if $k=1$ or $4$. If it is not true counter example would be appreciated. Thanks in advance.
2
votes
3answers
60 views

$\frac{1}{{{a_1}}} + \frac{1}{{{a_2}}} + \cdots + \frac{1}{{{a_n}}} < 2$

If ${{a}_{1}},{{a}_{2}},\ldots ,{{a}_{n}}$ are distinct odd natural numbers not divisible by any prime greater than 5, then show that $\frac{1}{{{a_1}}} + \frac{1}{{{a_2}}} + \cdots + ...
3
votes
3answers
33 views

Proof that $\sum_{d|m} |\mu(d)|=2^n$, where $n$ is the number of distinct prime divisors of $m$?

Given an integer $m$ such that $n$ is denoting the distinct prime divisors of $m$, is there a proof that the sum over the divisors of m of the absolute value of the Möbius function $\mu(d)$ is equal ...
1
vote
1answer
49 views

Show that there are no solutions to $x^2 + y^2 = 3z^2$ in $\Bbb{Z}$

I'm attempting to work through some of the questions in Whitelaw's "Introduction to Abstract Algebra" but am having some difficulty. The question is as follows Show that $\forall n \in \Bbb{Z},$ ...
0
votes
2answers
23 views

Proving that a common divisor of two variables is also a divisor of the sum of the two variables

if $k~|~a$ and $k~|~b$ then $k~|~as+bt$ for all $s,t \in \mathbb{Z}$ is what I'm trying to prove so I thought I should start by proving that $k~|~a+b$ if $k~|~a$ and $k~|~b$. since $a = \prod ...
5
votes
1answer
72 views

If $a \in \mathbb{Z}_5$ and $a \equiv \pm1 \text{ }(\text{mod }5)$, does there exist $x \in \mathbb{Z}_5$ where $x^2 = a$?

If $a \in \mathbb{Z}_5$ and $a \equiv \pm1 \text{ }(\text{mod }5)$, does there exist $x \in \mathbb{Z}_5$ where $x^2 = a$? I know we want to use Hensel's Lemma somehow to assess this question, but I'm ...
2
votes
2answers
37 views

If the sequence $ x_{n} $ converges to L, then $\lim_{k\to \infty}x_{k+1} = L $

Can someone read this proof and let me know if it is correct? If the sequence $ x_{n} $ converges to $L$, then $$\lim_{k\to \infty}x_{k+1} = L $$ Proof. Let $ \epsilon > 0$, and suppose ...
0
votes
3answers
57 views

Solve the following equation in $\mathbb{Z}_{16}$

I have this equation $\hat{5}x = \hat{6}$ in $\mathbb{Z}_{16}$. I'm not good at all at modular arithemetic. So far I just figured it out that $\hat{5}x = 6+16k, k\in \mathbb{Z}$.
4
votes
3answers
61 views

Quick, self-contained way to see why $\left({{-1}\over p}\right) = 1$?

Let $p$ be a prime number congruent to $1$ modulo $4$. What is a quick and self-contained way to see why$$\left({{-1}\over p}\right) = 1?$$
0
votes
1answer
53 views

How to solve this kind of Olympiad problems?

This kind of question is often asked in olympiads: Find the remainder when $a^n$ is divided by b where n is a very large number and a and b are whole numbers. What is the general trick to ...
2
votes
1answer
45 views

Given $p$ prime for some $p$ deduce $2p+1$ prime

Given $p=33179$ and $2^{2p+1}\equiv 2\; \pmod{2p+1}$, deduce $2p+1$ is prime. All I can think of is using Fermat's little theorem: $2^{2p}\equiv 1\pmod{2p+1}$ which just tells me it may be prime.
1
vote
1answer
33 views

root of quadratic equation in $Z_n$

I want to find criterion on $n$ satisfying this statement: "there is $x \in \mathbb{Z} _n$ such that $x^2 = a$". In case that $a=-1$, it is well known that (1) if $4k+1$ is prime, $n=4k+1$ satisfy ...
3
votes
1answer
78 views

How to prove that $n! = n^n - C_{n,1} (n-1)^n +C_{n,2} (n-2)^n - \cdots $?

How to prove that $n! = n^n - C_{n,1} (n-1)^n +C_{n,2} (n-2)^n - \cdots\,{} $? I faced this problem when trying to find the number of onto functions possible from one set having n elements to ...
1
vote
2answers
43 views

Help answering Pell Equation questions

I understand the Pell equation is $$x^{2}-dy^{2}=1$$ However I don't understand how to use this to get $(x,y)$ for these questions. 1) Find a nontrivial solution of $x^{2} − 3y^{2} = 1.$ 2) Find ...
2
votes
3answers
57 views

Show that $\gcd(a,b)=d\Rightarrow\gcd(a^2,b^2)=d^2\ $ [duplicate]

Show that if $\gcd(a,b)=d\Rightarrow\gcd(a^2,b^2)=d^2\ $ $\gcd(a,b)=d\Rightarrow\ d\mid a,b\Rightarrow\ \ d^2\mid a^2,b^2\Rightarrow\ d^2\mid\gcd(a^2,b^2)$. But to complete the proof we must show ...
0
votes
0answers
39 views

How to generate the sequence of prime building blocks of the colossally abundant numbers: $2, 3, 2, 5, 2, 3, 7, 2, 11, 13, 2, 3, 5, 17, 19, 23, 2,…$

This is the sequence of prime numbers which are the elementary building blocks for the superior highly composite numbers: $2, 3, 2, 5, 2, 3, 7, 2, 11, 13, 2, 3, 5, 17, 19, 2, 23, 7, 29, 3, 31, 2, 37, ...
0
votes
1answer
10 views

Factors/divisibility of monotonically-increasing integer polynomial

For positive integers $n$ and $x$, let $f_n(x)$ be a polynomial in $x$ of degree $n-1$, such that $f_n(x)$ is monotonically increasing for increasing $x \ge 1$. Now assume that there exist positive ...
3
votes
1answer
70 views

How do I count the solutions of $m^2 + m n + n^2 = T$?

I've come across this problem in my studies. I was wondering if there is a better algorithm for it: Given a fixed positive integer $T$, count the solutions of $$n^2 + n m + m^2 = T$$ where $m$ and $n$ ...
5
votes
1answer
260 views

Limit of Euler's Totient function

Clearly if $p$ is prime, the sequence $\frac{\phi(p)}{p} \rightarrow 1$. In general, however, if $s_n \in S \subseteq \mathbb{N}$, we are not even guaranteed of the existence of: $\displaystyle ...
1
vote
0answers
38 views

More efficient RSA using Chinese Remainder Theorem

Is there a way to increase the efficiency of the RSA algorithm by incorporating elements of the Chinese Remainder Theorem?
1
vote
0answers
36 views

Solving $x^2\equiv b \mod p$ for $p$ prime

How do I go about solving $x^2\equiv 116 \mod 587$ for $x$? I know that 587 is prime. How would I get started? I know $116= 2^2\cdot 29$ I think if I can solve $116^{147}\mod 587$, then I will have ...
0
votes
2answers
56 views

How do I factor $670726081$ if I have the informations that $33335^2\equiv670705093^2 \pmod{670726081}$?

How do I factor $670726081$ if I have the informations that $33335^2\equiv670705093^2 \pmod{670726081}$? I know that $\gcd(33335+670705093,670726081)$ is a nontrivial factor of $670726081$
0
votes
1answer
13 views

$a^2\equiv b^2\pmod n$ and $a\not\equiv \pm b\pmod n\implies\gcd(a+b,n)$ is a factor of $n$?

Suppose $a^2\equiv b^2\pmod n $ and that $a\not\equiv \pm b\pmod n$. How to then show that $\gcd(a+b,n)$ is a (nontrivial) factor of $n$? Hint to get started please.
0
votes
2answers
42 views

solve $x^2 -4x +13 \equiv 0 \pmod{81}$?

How do I solve $x^2 -4x +13 \equiv o \pmod{81}$ ? I know that this is the same as $x^2 -4x +13 \equiv x^2 + 2x + 1 \equiv (x +1)^2\equiv 0\pmod{3^4}$ but why is $x \equiv -1\pmod{3}$ the only ...
1
vote
2answers
55 views

How to derive identities [duplicate]

For example: $(a+b)^2 = a^2 + b^2 + 2ab$ $(a+b)^3 = a^3 + b^3 + 3ab(a+b)$ So my doubt regarding these identities are why does the identity differ when the power is changed and is there any ...
0
votes
1answer
36 views

A point whose coordinates are both integers is called a lattice point. How many lattice points lie on the hyperbola $x^2 -y^2 = 2000^2$

I found this answer here on AoPS. I agree with the answer till it multiplies $49$ by $2$. I think it should be multiplied by $4$ since there are $4$ possible cases: 1) $x+y, x-y$ is positive. 2) ...
1
vote
5answers
62 views

Does excluding or including zero from the definitions of “positive” and “negative” make any consequential difference in mathematics?

I was absolutely certain that zero was both positive and negative. And zero was neither strictly positive nor strictly negative. But today I made a few Google searches, and they all say the same ...
1
vote
1answer
49 views

How many numbers $m$ satisfy $1 ≤ m ≤ n$ and $\gcd (m, n) = 1$?

Let $n = p^2 q$ where $p$ and $q$ are distinct prime numbers. How many numbers $m$ satisfy $1 \leq m \leq n$ and $\gcd (m, n) = 1$? Note that $\gcd (m, n)$ is the greatest common divisor of $m$ and ...
6
votes
1answer
111 views

Solve $x^2 = 2^n + 3^n + 6^n$ over positive integers.

Solve $x^2 = 2^n + 3^n + 6^n$ over positive integers. I have found the solution $(x, n) = (7, 2)$. I have tried all $n$'s till $6$ and no other seem to be there. Taking $\pmod{10}$, I have been ...
2
votes
5answers
397 views

Divisibility via Induction: $8^n\mid (4n)!$ [duplicate]

I have to prove by induction the following fact: Show that $(4n)!$ is divisible by $8^n$. My stab at the solution: I have a slightly bad feeling about this solution and I would like if someone ...
1
vote
2answers
22 views

Show that if $\gcd(a,pq)=1$ and $g=\gcd (p-1, q-1)$ then $a^{\frac{(p-1)(q-1)}{g}}\equiv 1 \pmod {pq}$.

Suppose $p\neq q$ are two primes and $g=\gcd (p-1, q-1)$ Show that if $\gcd(a,pq)=1$, then $$a^{\frac{(p-1)(q-1)}{g}}\equiv 1 \pmod {pq}$$ Hi, how to do? I have no idea how to begin, Thanks.
0
votes
1answer
20 views

Simple Formula to workout intervals

Say we have scale from $1$ to $12$ We pick two numbers on this scale and trying to figure the shortest distance. Say $x_1 = 2, x_2 = 4$ and we need to figure out y which in this case would be $y = 2$ ...
1
vote
3answers
67 views

Use induction to prove that that $8^{n} | (4n)!$ for all positive integers $n$

Use induction to prove that that $8^{n} | (4n)!$ for all positive integers $n$ So far I have: Base case (n = 1) = $8^{1} | (4(1))!$ = $8 | 24$ which is true. Induction Step: $8^{n + 1} | (4(n + ...
3
votes
1answer
52 views

Occurence of number $1$ in the sequence $a_n=2^n$

So I was just calculating the terms of the sequence $a_n=2^n$ for $n=1,2,...50$ and discovered that among the first fifty terms there is $31$ term that has number $1$ in itself (in base $10$, of ...
1
vote
4answers
65 views

Find all pairs of prime numbers $p, q$ such that $p+q = 18(p−q)$.

Find all pairs of prime numbers $p, q$ such that $p+q = 18(p−q)$. It is clear that $p-q$ must be an even number since if we consider $q$ as $2$, we won't get any solution. So any pair of odd prime ...
1
vote
0answers
14 views

Congruences with LCM and Relatively Prime Numbers

How do I verify that if $a \equiv b\pmod{n_1}$ and $a \equiv b\pmod{n_2}$, then $a \equiv b \pmod n$, where the integer $n = \operatorname{lcm} (n_1, n_2)$. Hence, whenever $n_1$ & $n_2$ are ...
0
votes
1answer
24 views

If you have one primitive element modulo n; is it possible to easily find all of them modulo n? [duplicate]

If you have one primitive element modulo n; is it possible to easily find all of them modulo n? I have tried to figure this out but doesn't seem to get the approach to use. Hoe do I go about it?
0
votes
3answers
29 views

Prove on Theory of Congruences

Prove in elementary way: Prove that if $ab \equiv cd \pmod n$ and $b \equiv d \pmod n$, with $\gcd(b,\ n) = 1$. Then how do I prove that $a \equiv c \pmod n$.
3
votes
3answers
44 views

Prove that $\varphi(m)+ \tau(m)\leqslant m+1$

Prove that $\varphi(m)+ \tau(m)\leqslant m+1$ where $m\in \mathbb N$ I wrote $m:=p_1^{\alpha_ 1}....p_s^{\alpha _s}$ $$\varphi(m)=p_1^{\alpha_1}(p_1-1)...p_s^{\alpha_s}(p_s-1)$$ ...
0
votes
0answers
17 views

If n has at least one primitive element, what is the total number of primitive elements modulo n? [duplicate]

If n has at least one primitive element, what is the total number of primitive elements modulo n? Do I need to do any calculation on this or what Am I supposed to know to solve this?
0
votes
0answers
21 views

Use Hensel's lemma to show that if $a^n\equiv 1\mod{p}$ then $\exists b$ $b^n\equiv 1\mod{p^r}$

Let $p$ be an odd prime, and let $n$ be a natural number such that $n\mid p-1$. Suppose $1\neq a\in\mathbb{Z}$ is such that $a^n\equiv 1\mod{p}$, and use Hensel's lemma to show that for any given ...
0
votes
1answer
18 views

Congruent powers implies numbers are congruent

Let $N\in\mathbb{N}$, and let $m,n$ be coprime. Also, suppose $a,b$ are relatively prime to $N$, and that $$ a^n\equiv b^n\mod{N},\ a^m\equiv b^m\mod{N} $$ I need to show that $a\equiv b\mod{N}$. I ...
1
vote
1answer
69 views

Is the numbers of primes that is sum of 2 + another prime is finite?

In order to have sum of $2$-primes to be a prime one of the primes must be the prime $2$. However the "distance" between adjacent primes increases as we search along the natural numbers. For example ...
-2
votes
0answers
36 views

Proving a is a quadratic residue using that there is some x∈Z so that ordp(x)=p−1

Let $p>2$ be an odd prime, and assume there is some $x\in \mathbb{Z}$ so that ${\rm ord }_p (x)=p−1$. Use this assumption to prove that: a) If $p$ is an odd prime, $p$ does not divide $a$, and $a$ ...
0
votes
0answers
12 views

The number of pairs of coprimes in a given range

Let $n_{11} \le a \le n_{12}$ and $n_{21} \le b \le n_{22}$ be integers. Is there a formula $f$ which gives the number of the pairs $\left<a,b\right>$ which are relatively prime, that is, ...
0
votes
3answers
39 views

Solutions to the diophantine equation $6x^2 - 6x - y^2 + y=0$?

Are there any positive integer solutions to the diophantine equation in the title other than $(1,1)$? This equation looks easy enough so it could be that there is some simple argument that shows ...
1
vote
2answers
35 views

Congruence Modulo involving factorials

How do I show that $23!\equiv 21! \pmod{101}$? I tried using a calculator but the numbers are so big that am finding it hard to prove. How can factorials be broken down so that they can be easily ...