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

learn more… | top users | synonyms (1)

1
vote
4answers
62 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
38 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 ...
1
vote
2answers
31 views

Proving a congrent modular

How do I show that $3^{1974}+5^{1974}\equiv 0 \pmod {13}$? I have tried feeding the values onto a calculator but they are so big to be computed. What is the best approach?
2
votes
1answer
70 views

Prove that a perfect square (also a perfect square backwards) is divisible by 121

Suppose that $n=x^2$ is a perfect square with an even number of base-10 digits. Assume that when n is written backwards, you get another perfect square $y^2$. Prove that 121|n. (Use the mod 11 ...
0
votes
2answers
36 views

Smallest positive integer n

The smallest positive integer $n$ with $24$ divisors (where $1$ and $n$ are also considered as divisors of $n$) is? As far as I know it can be solved like this: prime factors of $24$ are : ...
2
votes
1answer
45 views

A conditional inequality which itself implies a sharper version of it [duplicate]

Problem: Given that $m, n$ are positive integers such that $\sqrt{7} -\frac{m}{n} > 0$. Then show that $\sqrt{7}-\frac{m}{n} > \frac{1}{mn}$. I have failed to do this fascinating problem. My ...
2
votes
0answers
43 views

How to improve this proof?

I was doing these two propositions and I do not feel 100% sure about them so I was wondering if I could get any help or advice. Thank you.
2
votes
3answers
98 views

Number of pairs of rational numbers that satisfy the given relation

The number of pairs $(x,y)$ that satisfy : $2x^2 + y^2 + 2xy - 2y + 2 = 0$ is a.) $0$ b.) $1$ c.) $2$ d.) None of the foregoing numbers My attempt : I am not well versed in number theory , thus I ...
0
votes
0answers
17 views

i'm confusing on power of x in modular equation..

From question 1, i thought that fermat's little theorem. a^p≡a ≡b^p ≡ b (mod p ) and because (a,p)=1=(b,p) , (a,p^2)=1=(b,p^2), a^(p^2)≡a≡b≡b^(p^2) mod p^2 but how can we know that a^p≡b^p mod ...
3
votes
3answers
409 views

Find all integer solutions to $\frac{1}{x} + \frac{1}{y} = \frac{2}{3}$

Find all integer solutions $(x, y)$ of the equation $$\frac{1}{x} + \frac{1}{y} = \frac{2}{3}$$ What have done is that: $$\frac{1}{x}= \frac{2y-3}{3y}$$ so, $$x=\frac{3y}{2y-3}$$ If $2y-3 = ...
0
votes
1answer
54 views

If $d>1$ is a squarefree integer, show that $x^2 - dy^2 = c$ gives some bounds in terms of a fundamental solution.

If $d>1$ is a squarefree integer, show that $x^2 - dy^2 = c$ gives some bounds in terms of a fundamental solution. I am not able to understand the question itself. What does it exactly mean ...
-1
votes
1answer
58 views

Square Root of $5$ mod $10^{9}+7$ [closed]

$My$ $Current$ $Knowledge:$ We can find it if 5 is a $Quadratic$ $residue$ modulo p and where p is prime and we can check it using $Euler$ $criterion$. I cannot able to find the root(5)mod 1000000007. ...
0
votes
0answers
23 views

Modular residue number theory problem.

Given large enough integer $N$ is there always $(\lceil\log N\rceil)^d$ pairs of integers $z,p$ where each of $p$ is distinct prime with $N<p$ and $z$ satisfies $z\bmod p<\frac{zN\bmod p}{N}$ ...
3
votes
1answer
122 views

Can we replace the upper limit condition of the Sieve of Eratosthenes $\sqrt{n}$ with the value $\sqrt{p}$ where $p$ is the last sieved prime $\lt n$?

By chance I stumbled upon the OEIS list A033677 of the smallest divisor of $n$ greater or equal to $\sqrt{n}$. Roughly speaking if we use the classic enhanced sieve of Eratosthenes, $\sqrt{n}$ is the ...
1
vote
0answers
30 views

prove that for any pair of natural, there is a power of 2 that separates the pair of natural

i need to prove that: $$ \forall i,j \in \{1, \_ ,N \} \subset \mathbb{N} \ \exists k \in \mathbb{N} / (r_{2^k}(i) \leq 2^{k-1} \wedge r_{2^k}(j) > 2^{k-1})\vee (r_{2^k}(i) > 2^{k-1} ...
8
votes
5answers
1k views

None of $3,5,7$ can divide $r^4+1$

Let $n=r^4+1$ for some $r$. Show that none of $3,5,$ and $7$ can divide $n$. I am thinking to use a corollary that "each prime divisor p of an integer of the form $(2m)^4+1$ has the form $8k+1$", but ...
2
votes
2answers
31 views

Prove that $36|n^{12k-6}-n^6$

Prove that if gcd(n,6)=1 and k>0, then $36|n^{12k-6}-n^6$. Idea: I want to show that $2|n^{12k-6}-n^6$ and $3|n^{12k-6}-n^6$. For the first part, since gcd(n,6)=1, n must be an odd number, so it ...
1
vote
0answers
25 views

Propositions about absolute value

I Have two propositions to prove and below are my proofs. Any helps or comments would be appreciated! Prop 1 For all x∈R, |x|^2 = x^2. Proof Let x∈R and suppose x≥0. By the definition of the ...
0
votes
1answer
36 views

Is the congruence $x^2\equiv n\;(mod\,m) $ has a solution?

It is possible that $ (\frac{n}{m})=1$ while the congruence $x^2\equiv n\;(mod\,m) $ has a solution: Is this true for every prime dividing n i am confusing about this problem can any one help me
0
votes
1answer
33 views

Show that $[\mathbb{Z}_n : m\mathbb{Z}_n] = \frac{n}{gcd(m,n)}$

Let $n$ be a positive integer, and let m be any integer. Show that $[\mathbb{Z}_n : m\mathbb{Z}_n] = \frac{n}{\gcd(m,n)}$. My understanding is that $[\mathbb{Z}_n : m\mathbb{Z}_n]$ represents the ...
0
votes
1answer
37 views

Find the inverses of 2,3,…,16 modulo 17. [closed]

I need to find the inverses of 2,3,...,16 modulo 17 and use to solve (a) 5x ≡ 9 (mod 17); (b) 11x ≡ 3 (mod 17). I found the inverse of 5 modulo 17, to be 7 modulo 17 and know to solve by multiplying ...
4
votes
2answers
118 views

Are there any number $n$ such that $a_n = 0 \mod (2n + 1) $ where $a_0 = 1, a_1 = 4, a_{n + 2}=3 a_{n + 1} - a_{n}$?

Define the sequence $a_n$ by the following. $$a_0 = 1, a_1 = 4,$$ $$a_{n + 2}=3 a_{n + 1} - a_{n}$$ $a_n ≠ 0 \mod (2n + 1)$ for $1 \le n \le 10^5 $. Are there any number $n$ such that ...
0
votes
5answers
70 views

Find remainder when $1^{5} + 2^{5} \cdots +100^{5}$ divided by 4

I'm studding D.M Burton & want to solve: Find remainder when $1^{5} + 2^{5} \cdots +100^{5}$ divided by $4$. . Please help me by giving your solution to it. I'm new comer to number theory so ...
1
vote
0answers
22 views

How to prove that $gxyz$ and $g(y-x)$ are perfect squares? [duplicate]

Let $x,y,z$ be positive integers such that $1/x-1/y=1/z$. Let $g=\gcd(x,y,z)$. Prove that $gxyz$ and $g(y-x)$ are perfect squares.
1
vote
5answers
48 views

Multiplication of three primitive roots

I have noticed that if I multiply three primitive roots of the same modulo it is still a primitive root in that modulo. But I cant manage to prove it or this isn't true? Let $x,y,z$ be primitive ...
0
votes
2answers
55 views

Given hcf and lcm find two numbers.

Let $G$ and $L$ be given positive integers. Prove that integers $x$ and $y$ exist satisfying $gcd(x,y)=G$ and $lcm[x,y]=L$ if and only if $G|L$. My attempt: $$x=\prod _{i=1}^kp_i^{\alpha _i}$$ ...
6
votes
2answers
83 views

Find all $n$ such that $\sqrt{5n+2}$ is an integer.

Here is my solution. There is no such $n$. If $n$ is odd, then, then $5n+2 \equiv 7 \pmod {10}$. Else, $5n+2 \equiv 2\pmod {10}$. But, the quadratic residues of $10$ are only $0,1,4,9,6,5$. ...
0
votes
3answers
73 views

Prove by strong induction that $3^n$ divides $a_n$ for all integers $n \ge 1$

Let $a_1 = 3, a_2 = 18$, and $a_n = 6a_{n-1} − 9a_{n-2}$ for each integer $n \ge 3$. Prove by strong induction that $3^n$ divides $a_n$ for all integers $n \ge 1$ I've done the base step and ih ...
0
votes
2answers
31 views

Show $66!\equiv 68 \pmod{71}$

The question asked to show $66!\equiv 68 \pmod{71}$. I start with using Wilson Theorem,I get $70!\equiv -1\pmod{71}$, next I try to write $70!=70*69*68*67*66!\equiv (-1)*(-2)*(-3)*(-4)*66! ...
0
votes
0answers
26 views

Are there any particular integers we are certain to arrive at by repeated application of $\lfloor(n-1)/2\rfloor$ on any positive integer $n$?

Suppose we pick an integer $n \in \mathbb{N}_{>0}$, and repeatedly apply the operation $\lfloor(n-1)/2\rfloor$ on it. We are guaranteed to eventually reach $0$, but are there any other small ...
1
vote
2answers
42 views

Convert time in seconds to 24-Hour clock and AM/PM clock [closed]

Maybe it is a basic problem but it confused me. How can we formulate a translation of given seconds to 24 hour clock or am/pm clock. For example; 77400 seconds is $21:30:0$ in 24 hour clock and ...
0
votes
0answers
40 views

Sum of all numbers less than equal to X relatively prime to all number less than Y

Here's a programming question probably needing lots of math: Given two integers X and Y, you need to find the sum of all positive integers less than or equal to X, which have no divisor smaller ...
0
votes
1answer
19 views

Order of x (modp) = 3 implies order of x+1 (modp) = 6

I'm not sure how to prove the statement. I know that $ord(x)=3$ implies that $p | (x^3-1)$ and $x^3-1 = (x^2+x+1)(x-1)$ and I also know that $ord(x) | (p-1)$, so p is of the form $3k+1$ for $k$ being ...
1
vote
1answer
25 views

Does “sum of divisors” function attain every value of the form $kn$?

By the "sum of divisors" function I mean the function $\sigma (n)= \sum_{d|n} d$. If we choose $k=1$ then it is not possible that we have $\sigma (n)=n$ because $n$ always has at least two divisors, ...
1
vote
2answers
55 views

How do I show that $2730$ divides $n^{13}-n$ for $n$ is integer?

I have tried to show that : $2730 |$ $n^{13}-n$ using fermat little theorem but i can't succeed or at a least to write $2730$ as $n^p-n$ . My question here : How do I show that $2730$ divides ...
1
vote
0answers
36 views

Value of $\sum^\infty \frac{1}{p_n !}$ =? [duplicate]

The sequence $$ \sum_{i=1}^{n} \frac{1}{p_i !}$$ with $p_i$ the i-th prime number is apparently convergent, since its strictly increasing and limited by $ e = \sum^\infty \frac{1}{n!}$. What is ...
0
votes
1answer
118 views

Multiply $3$ or more numbers at the same time.

Consider a set of numbers $N \in \Bbb N $ in the range $[1, M[$, where all the numbers are co-prime with $M$ How can we easily multiply certain numbers of that set at the same time, where computation ...
0
votes
1answer
21 views

greatest common divisor properties

Let $f(N,x)$ is $N$ repeated $x$ times. So $f(123,2)=123123$ and $f(123,3)=123123123$ In the problem we are given $a$ and $b$ and $N$ and we need to calculate $\gcd(f(N,a),f(N,b))$. How do we prove ...
1
vote
0answers
22 views

Is there Modular 's cycling property?

Find the number of incongruent solution of the congruence $$x^5+10 \equiv 0 \pmod {11^4}$$ this is problem When I try to solve it, in $\mod 11$, $$x \equiv 1,2,3,4,5,6,7,8,9,10 \pmod{11}$$ ...