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

learn more… | top users | synonyms (1)

0
votes
0answers
18 views

If the euclidean algorithm is used to solve an equation ( i.e., $ax = b \mod(z)$) is the solution unique?

I have solved such an equation using the euclidean algorithm. However, unlike other methods, this gives one solution. Is this just one solution or the only solution. Help is much appreciated. Thank ...
0
votes
1answer
29 views

Prove that $ax \equiv 1 \bmod n \implies \gcd(a,n) = 1$.

I'm trying to prove the following but having difficulties. Suppose $a,x \in \mathbb{Z}$ and $n \in \mathbb{N}$ then prove if $ax \equiv 1 \mod n$ then $a$ is coprime to $n$. I know what it ...
2
votes
1answer
46 views

Suppose $m \mid 2^p - 1$. Show that $m \equiv 1 \pmod {2p}$.

I would like to get help with this proof: Let $p\ge3$ be a prime number, and let $m$ be a divisor of $2^{p}-1$, Prove that $m\equiv 1\ (mod\ 2p)$. I thought about proving that $m=1\ mod\ p$, ...
1
vote
0answers
95 views

$ x^2+y^2+z^2=k(xy+yz+zx) $

Let $A $ be a set of all positive integers so that if $ n\in A $ then $n-1$ has at least one prime divisor $p\equiv 2( mod 3)$ such that $v_p(n-1)$ is odd and let $B$ be a set of all positive ...
3
votes
1answer
48 views

Wilson's Theorem proof

How do I prove Wilson's Theorem $$\large{(p-1)! \equiv -1 \pmod p}$$ using Euler's theorem $$ \large{a^{\phi(n)} \equiv 1 \pmod n }$$ where $ \large{\phi(n)} $ denotes Euler's Totient function? ...
4
votes
1answer
49 views

Is there a counterexample? $\forall p \in \Bbb P\ ,\ p\gt 61\ ,\ \exists\ r1,r2\ \in \{\ Primitive\ Roots\ Modulo\ p\ \}\ /\ r1+r2 = NextPrime(p)$

This is the weirdest thing I have observed so far! Take the set of Primitive Roots Modulo p (link to definition here) of a prime number $p$, $Pr(p)$. For those primes $p \gt 61$ there is always a pair ...
7
votes
1answer
44 views

Infinite solutions for $(\frac{n+1}{n})^a\cdot (\frac{m+1}{m})^b = 2$

Given $(\frac{n+1}{n})^a\cdot (\frac{m+1}{m})^b = 2$ where a, b, n, and m are all positive integers, are there infinitely many solutions $(a,b,n,m)$?
0
votes
1answer
26 views

Is it possible to exhibit a collection of sets

Let a subset $D$ of the natural numbers be called convergent or divergent when the associated series $\sum_{d \in D} \frac{1}{d}$ converges or diverges. Define a topology on $\Bbb{N}$ by defining the ...
0
votes
0answers
21 views

Counting the number of elements $x$ between $p$ and $p^2$ where lpf$(x(x+2))=7$

Let $p > 7$ be any prime. Let $f_7(p)$ be a function that counts the number of elements $x$ where $p < x < p^2$ and lpf$(x(x+2))=7$ where lpf is the least prime factor. It has been ...
6
votes
2answers
78 views

When is the sum of divisors a perfect square?

For $n=3$, $\sigma(n)=4$, a perfect square. Calculating further was not yielding positive results. I was wondering is there a way to find all such an $n$, like some algorithm? We know that if ...
2
votes
1answer
31 views

Questions on integer-valued polynomials

An integer-valued polynomial or numerical polynomial is a polynomial $f \in \mathbb Q[x]$ with the property that $f(\mathbb Z)\subseteq \mathbb Z$. The set of numerical polynomials forms a subring ...
-3
votes
5answers
225 views

What is zero? Irrational or rational or it have both the properties? [duplicate]

We say, A number is rational if it can be represented as $\frac{p}{q}$ with $p,q \in \mathbb Z$ and $q\neq 0$. Any number which doesn't fulfill the above conditions is irrational. What ...
4
votes
1answer
47 views

A functional equation with no term outside functions

Find all $f:\mathbb{N} \rightarrow \mathbb{N}$ satisfying $$f(m-n+f(n))=f(m)+f(n)$$ for all $m,n \in \mathbb{N}.$ I have no idea about how to find them, because there are no terms outside of the ...
1
vote
1answer
34 views

Solving the congruence $3x^2 + 6x + 1 \equiv 0 \pmod {19}$

I tried to solve this equation but without a success: $3x^{2}+6x+1 \equiv 0 \pmod {19}$ I concluded hat $x(x+2)\equiv 6 \pmod{19}$, the only way i think to solve this is by just trying all the ...
2
votes
0answers
62 views

Need help in understanding the question. Elemntary number theory

I have this question in my home assignment. I contains two parts and I don't quite understand what is the difference between them.The question is: Let $n > 2$ be an integer such that ...
4
votes
2answers
29 views

Question about proof of Lucas Primality test

Lucas Primality Test. Suppose that $n > 1$ and $a$ are integers with $a^{n-1} \equiv 1 \mod n$ and $a^{(n-1)/p} \not\equiv 1$ for all primes $p \mid n-1.$ Then $n$ is prime. Proof. Suppose that ...
1
vote
2answers
39 views

Why having $ma+np=1$ implies that $m$ is the inverse?

I'm reading Stilwell's: Elements of Number Theory. In here: I don't understand why having $ma+np=1$ implies that $m$ is the inverse.
5
votes
3answers
126 views

Factoring product of two primes from solutions of congruence

The algorithm purposed to play a fair game of heads or tails over the phone given here claims that knowing the four solutions to $$ x^2 \equiv a^2 \pmod n$$ would allow us to factor $n$ where $n$ is ...
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$, ...
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
100 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
83 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
92 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
135 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
317 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
71 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: ...
6
votes
7answers
136 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
64 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 ...