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

learn more… | top users | synonyms (1)

1
vote
1answer
46 views

Prove or disprove: If $a^2 \mid bc$, then $a \mid b$ or $a \mid c$

Prove or disprove: If $a^2 \mid bc$, then $a \mid b$ or $a \mid c$. I have not been able to find a counter example so I am thinking it may be true. I started by thinking that since $a^2 \mid bc$, ...
0
votes
0answers
44 views

Reduction of trigonometric functions to $x$ power [closed]

$$\huge{(\sqrt{1 - \sin^2x})^{2^{x^\sqrt{1 - \sin^2x}}}}$$ $x > 0$ if the domain of $x$ is between $1$ and $1.5$
1
vote
2answers
58 views

Let $m = 4^n+1$ for some integer $n \geqslant 1.$ Prove that $3^{(m-1)/2} \equiv -1 \pmod m$ if and only if $m$ is prime.

Let $m = 4^n+1$ for some integer $n \geqslant 1.$ Prove that $3^{(m-1)/2} \equiv -1 \pmod m$ if and only if $m$ is prime. $(\mathbb{Z} / m \mathbb{Z})^{\ast} =$ unit group modulo $m.$ Suppose that ...
2
votes
1answer
23 views

Find the first Poulet number

A Poulet number (OEIS $A001567$) is called a composite number $n$ such that $2^{n-1}−1$ is divisible by $n$. The first such a numbers are: $$ 341, 561, 645, 1105, \ldots $$ Question: How to prove ...
4
votes
1answer
27 views

$x-1$ in base $x$ counting systems

Please excuse the lack of expertise. I'm not a mathematician, nor have I studied it since high school. I was thinking about how all the digits of multiples of $9$ summed equal a multiple of $9$. I ...
0
votes
2answers
33 views

For which primes $p \ne 2,5$ does the congruence $x^2 \equiv 10 \mod p$ have a solution?

For which primes $p \ne 2,5$ does the congruence $x^2 \equiv 10 \mod p$ have a solution? Using the Legendre symbol, we have $\left(\dfrac{10}{p}\right) = \left(\dfrac{5}{p}\right) ...
1
vote
2answers
25 views

Sequence of perfect squares

Let $a,b\in \mathbb{N}$. Prove that, if $a$ is quadratic residue modulo $b$, then sequence $(a+kb)$, $k\in \mathbb{N}$, has infinite amount of perfect squares. How should I approach this ...
2
votes
6answers
99 views

Prove that $7$ divides $1 + 2^{(2^n)} + 2^{(2^{n+1})}$ by induction

Prove that $7$ divides $1 + 2^{(2^n)} + 2^{(2^{n+1})}$ by induction. I ran into the above problem. The base case $n=1$ gives $21$ which is divisible by $7$. Now assume it is true for $n$. Then for ...
0
votes
1answer
48 views

Problem with Recurrence Relations

A particle P executes a random walk on the line above such that when it is at point $n$ ($1 \leq n \leq 9$, $n$ a non-negative integer), it has a probability of $0.4$ of moving to $n+1$ and a ...
0
votes
1answer
21 views

Counting the spokes

I’ve been playing around with wheel factorization (Wikipedia link) and wanted to know how many spokes there are in a given wheel. For a 2-7 wheel the circumference of this would be 210 and then I can ...
3
votes
5answers
127 views

Solve $x^{2}\equiv 24 \mod 125$

Here's a congruence I'm trying to solve: $$x^2\equiv24 \mod 125$$ What are the techniques I could use to solve it? I know about Euler's phi function, Fermat's little theorem and Chinese remainder ...
0
votes
4answers
81 views

Find values of $a$ in $\{2,3,\dots ,9999\}$ such that $a^2-a$ is divisible by 10000.

Today was my entrance test for BSc.(Hons.) in that there was a question which I was unable to solve. I'm asking this question here because I think that the question was wrong(most probably I'm wrong). ...
1
vote
0answers
89 views

Conjecture: for even n without primitive roots modulo n, the set of $m \in Max(ord_n(k))$ contains one pair of primes $p_1+p_2=n$ (Goldbach)

Conjecture: for those n even numbers that do not have primitive roots modulo n ,$Pr(n)$, the set $M(n)$ of those $k$ having a maximum multiplicative order $ord_n(k)$ contains at least a pair of primes ...
2
votes
0answers
24 views

the number of solutions of the congruence $x^2 \equiv a \pmod m$ is $\prod_{p \mid m} \left(1+ \left(\dfrac{a}{p} \right) \right).$

Suppose that $m$ is odd. Show that if $\gcd(a,p) = 1$ then the number of solutions of the congruence $x^2 \equiv a \mod m$ is $\displaystyle \prod_{p \mid m} \left(1+ \left(\dfrac{a}{p} \right) ...
2
votes
2answers
51 views

prime number problem:

How can I show that; For any prime $p,$ there exist $u, v\in\mathbb{N}\setminus{\{p\}}$ ( and depend on $p$) such that $\color{Purple}{p\mid uv}$ and both ...
3
votes
1answer
31 views

For which primes is $-2$ a quadratic residue?

For which primes is $-2$ a quadratic residue? We are trying to find primes that have solution for $x^2 \equiv -2 \mod p.$ Using the Lagrange symbol I know that $2$ is a quadratic residue when $p ...
1
vote
2answers
41 views

What does “maximum order elements to mod n” mean for a number n without primitive roots modulo n?

I apologize because probably this is trivial, but I do not understand the concept: "maximum order elements to mod n for n". This is the context: in the Wikipedia in the primitive roots modulo ...
0
votes
1answer
16 views

In $\mathbb{Z_6}[x]$, factor each of the following into two polynomials of degree $1: x, x+2,x+3$

This question is pretty confusing: In $\mathbb{Z_6}[x]$, factor each of the following into two polynomials of degree $1: x, x+2,x+3$ so for example, do i have to find two polynomials that equal ...
3
votes
2answers
134 views

Sum of the digits of a perfect square

Prove that the sum of the digits of a perfect square can't be 2, 3, 5 , 6, or 8. I'm completely stumped on this one, how would I go about proving it?
6
votes
2answers
72 views

Show that $\gcd(a^2, b^2) = \gcd(a,b)^2$

Show that $\gcd(a^2, b^2) = \gcd(a,b)^2$. This is what I have done so far: Let $d = \gcd(a,b)$. Then $d=ax+by$ for some $x,y$. Then $d^2 =(ax+by)^2 = a^2x^2 + 2axby+b^2y^2$. I am trying to create a ...
18
votes
2answers
314 views

Without using Heegner-Stark-Baker, $\mathbb{Q}(\sqrt{-11})$ has class number $1$.

Prove that $\mathbb{Q}(\sqrt{-11})$ is of class number $1$. I have found that the ideal $(2)$ of the integer ring $\mathbb{Z}[(1 + \sqrt{-11})/2]$ of $\mathbb{Q}(\sqrt{-11})$ is a prime ideal. ...
1
vote
1answer
38 views

Prove or disprove: If $a\mid b+ c$ and $a \mid b - c$ and $a$ is odd, then $a \mid b$.

Prove or disprove: If $a\mid b + c$ and $a\mid b - c$ and $a$ is odd, then $a\mid b$. I cannot seem to find a counterexample so I am thinking it might be true, but cannot prove it either. This is ...
7
votes
2answers
112 views

Prove: if $n\mid 7^n+6^n$ and $n>1$, then $13\mid n$

Prove: if $n\mid 7^n+6^n$ and $n>1$, then $13\mid n$ Let $p$ be the least prime number such that $p\mid n$. And I want to show that $p=13$ Let $d$ be the least number such that: $14^d\equiv 0 ...
0
votes
3answers
49 views

Let $n \in \Bbb N$. Find the inverse of $n \pmod {n + 1}$

Let $n \in \Bbb N$. Find the inverse of $n \pmod {n + 1}$ I tried answering the question and got $n+1 \pmod 1$, is this correct? Do I need to use Pell's equation?
9
votes
8answers
129 views

Find the integer x: $x \equiv 8^{38} \pmod {210}$

Find the integer x: $x \equiv 8^{38} \pmod {210}$ I broke the top into prime mods: $$x \equiv 8^{38} \pmod 3$$ $$x \equiv 8^{38} \pmod {70}$$ But $x \equiv 8^{38} \pmod {70}$ can be broken up ...
3
votes
1answer
68 views

Solving a Diophantine equation3

The Diophantine equation that I have to solve is: $$343x^2-27y^2=1$$ This question has already been posted by other user but it has not received an answer. I proved to solve it. This is my attempt: ...
5
votes
7answers
122 views

How to prove that $2^{n+2}+3^{2n+1}$ is divisible by 7 using induction?

I want to prove that $2^{n+2}+3^{2n+1}$ is divisible by 7 using induction. My first step is replace $n$ with $1$. $2^{1+2}+3^{2(1)+1}$ $2^3+3^3$ $8+27$ $35 = 7\times 5$ The next step is assume ...
0
votes
1answer
42 views

Using Bezout's identity

After obtaining $gcd(96,40)=8=5\times40-2\times96$ I don't understand how to continue the following question: Does the equation $96x+40y=16$ have integer solutions $(x,y)$? If yes, find them ...
6
votes
2answers
63 views

Find the number of ordered pairs $(a,b)$ if $\text{lcm}(a,b)=2^3 \cdot 3^5 \cdot 11^7 $

How many ordered pairs $(a,b)$ are there such that $$\text{lcm}(a,b)=2^3 \cdot 3^5 \cdot 11^7 $$ I tried using a number theoretic approach, but couldn't solve it. Moreover, it was given in ...
0
votes
0answers
13 views

How to prove that $\mbox{gcd}(2^a-1,2^b-1)=2^{\mbox{gcd}(a,b)}-1$? [duplicate]

How to prove that $$\mbox{gcd}(2^a-1,2^b-1)=2^{\gcd(a,b)}-1$$?
1
vote
1answer
27 views

Standard definition for $a$ being congurent to $b$ mod $n$

My text puts the definition for $$a\equiv b \bmod n$$ as $$n\mid(a-b).$$ On the other hand, certain sources puts the definition as $$n\mid(b-a).$$ Which exactly is the standard notation or is there a ...
2
votes
1answer
42 views

How prove this fact about consecutive square numbers?

I saw somewhere that the sum of three consecutive squares minus $2$ is divisible by $3$. For example, $$2^2+3^2+4^2-2=4+9+16-2=27=3\cdot 9$$ But, I'm not sure how to give proof for this "property" of ...
1
vote
1answer
29 views

Integer division through multiplication by reciprocal

Please help me to understand (prove) why the following statement is true. For any natural number $w > 0$ and divisor $b \in \left[ 1, 2^w \right)$, if we define a natural number $inv(b)$ such that ...
1
vote
2answers
36 views

Prove: if $a$ is a square mod $p,q$, then it is a square mod $pq$

For distinct odd primes $p,q$, if $x^2\equiv a \pmod {\! p}$ is solvable and $x^2\equiv a \pmod {\!q}$ is solvable, then $x^2\equiv a \pmod {\! pq}$ is solvable. Here, I am also assuming neither $p$ ...
1
vote
4answers
82 views

If the sum of two squares is divisible by $7$, both numbers are divisible by $7$ [closed]

How do I prove that if $7\mid a^2+b^2$, then $7\mid a$ and $7\mid b$? I am not allowed to use modular arithmetic. Assuming $7$ divides $a^2+b^2$, how do I prove that the sum of the squares of ...
0
votes
1answer
24 views

Show that 2 is not primitive modulo $p=2^{2^n}+1$ for $n\ge 2$, p prime.

Show that 2 is not primitive modulo $p=2^{2^n}+1$ for $n\ge 2$, p prime. My problem is that I can't prove by contradiction, because logically I can't say "suppose there isn't $m<\phi(p)$ such that ...
0
votes
2answers
35 views

How to replace these two equations by one equation.

Let $x$ be natural number such that $\begin{cases} x=5k+3\\ x=3l+1 \end{cases}$ $k,l\in \Bbb N$ WolframAlpha says that $x=15n+13, n\in \Bbb N$. That's right because: $15n+13=5(3n+2)+3=5k+3$ ...
1
vote
1answer
22 views

Check membership in set of bisquares

A bisquare is a number which can be expressed as $p^2 + q^2$ where $p,q\in\mathbb{W} $. Given a number, how can you quickly tell if it is a bisquare or not? Is it even possible to do so without using ...
1
vote
0answers
29 views

Show 3 is a primitive root modulo $7^n$ for $n\in \Bbb{N}$. [duplicate]

I tried induction but got stuck. For $n=1$ it is true. Suppose it holds for $n$, i.e, the order of 3 is $\phi(7^n)$. Now I should prove it for $\phi(7^{n+1})=6\cdot 7^n$. $7^n\mid3^{6\cdot 7^n}-1$. ...
1
vote
1answer
42 views

Show that there are infinitely many primes $p$ of the form $p=a^2+b^2+c^2+1$

I know that any prime can be written as the sum of four squares. But I don't know how to know one of these squares is $0$.
1
vote
1answer
17 views

How are equation of that form $a^x\equiv b \mod n$ often named?

How are equation of that form $a^x\equiv b \mod n$ usually named? I am trying to solve $7^x\equiv 6 \mod 17$ but I am having troubles doing so for I don't know enough properties of this kind of ...
0
votes
0answers
29 views

Can you help me write this $n^n$ related sequence so that the sum over divisors notation is used?

I need help writing the following sequence: $$a(n)=0,\frac{\log (2)}{2},\frac{1}{3} \log \left(\frac{9}{2}\right),\frac{1}{4} \log \left(\frac{32}{3}\right),\frac{1}{5} \log ...
2
votes
2answers
29 views

Check for an equivalence relation on the integers

Given the set of integer $\mathbb Z$, define $\sim$ as $x\sim y$ precisely when $2$ divides $x-y$. I'm having a hard time showing that the three properties of an equivalence relation hold. Any help ...
3
votes
2answers
54 views

Prove that the sums of the reciprocals of the primes diverge using $\frac{1}{p_{j+1}}+\frac{1}{p_{j+2}}+\frac{1}{p_{j+3}}+\cdots>\frac{1}{2}$

Prove that the sum of the reciprocals of the primes diverge, i.e show that: $$\frac{1}{p_1}+\frac{1}{p_2}+\frac{1}{p_3}+... Diverges$$ The hint I got: To show that the sum of the reciprocals of the ...
2
votes
1answer
26 views

Proving that $n|x^ {φ(n)/2} − 1$ for every $x$ coprime to $n$.

Let $n \in \Bbb{N}$ for which there exist two coprime numbers bigger than 2 dividing n. Show that for every x coprime to n we have $n|x^ {\phi(n)/2} − 1$. Conclude that there is no primitive root ...
1
vote
1answer
39 views

A question on Primes in Arithmetic Progression

We know that an arithmetic progression has to have a composite number since there are arbitrarily large gaps between primes. But I was wondering whether the following construction is possible: Can ...
0
votes
0answers
13 views

Are integral combination and linear combination the one and the same in the field of number theory?

My question is a trivial question as to the exactness of the meaning of integral and linear in the study of the number theory. Do they hold the same meaning?
1
vote
0answers
25 views

Estimating the number of elements with a given least prime factor in a sequence of consecutive integers

Let $a,n$ be any positive integers. Let $\varphi(x)$ be the Euler totient function. It seems to me that the number of elements $x$ with $a \le x < a+n$ that have a given least prime factor will ...
2
votes
1answer
54 views

For what values of $n$ , does $7 \mid 5^n+1$

$7 \mid 5^n+1$ implies $5^n+1=7a$ for some integer $a$ i.e $5^n=7a-1$ Now , $5^n$ is an integer which always ends with $5$ [for any integer $n$]. Thus , $7a-1$ must also end with $5$.But , this is ...
1
vote
2answers
45 views

2 questions in Number Theory about primitive roots/quadratic residue

I tried to solve this 2 questions but without a success: Is $13$ a sixth power modulo $289$? Find all the solutions of $x^{8}\equiv 3\mod 13$ In question 1, I tried to see if $13$ is a quadratic ...