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

learn more… | top users | synonyms (1)

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 ...
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
72 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
38 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
99 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
55 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
123 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
38 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
119 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
73 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
59 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
43 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
56 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}$$ ...
3
votes
0answers
277 views

The Divisors of $s(2s+1)$ and Primes $2n+1$ and $3n+1$ part 1

I want to check my math (and proof) on the following claim. The claim is by way of a computer search and a "hunch". claim: If $s$ is a prime number I write $\varphi_{s} =s(2s+1)$. Let $\tau$ be ...
0
votes
3answers
30 views

Divisors and Greatest Common Divisors

Prove that for every integer $n$ is of the form $4t, 4t+1, 4t+2$ or $4t+3$ for some $t ∈ Z$. How would one approach this problem? Would it be somewhat similar to induction when one would assume ...
2
votes
1answer
41 views

An odd positive integer is the product of $n$ distinct primes. In how many ways can it be represented as the difference of two squares?

An odd positive integer is the product of $n$ distinct primes. In how many ways can it be represented as the difference of two squares? My formulation of the question: $$x^2 - y^2 = ...
8
votes
2answers
532 views

Does a finite sum of distinct prime reciprocals always give an irreducible fraction?

If we add any finite number of any distinct prime reciprocals, will the result always be an irreducible fraction? If not, is there any bound on the value of a greatest common divisor for the ...