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

learn more… | top users | synonyms

0
votes
0answers
39 views

Proof of Gauss formula to find number of Primes

How did gauss found this formula to find the number of primes when he was 15 , can anyone provide me the proof.
7
votes
0answers
164 views

Number of ways to express a binary number in a certain way

So I'm working on a problem where I get to a point where I have to count the number of solutions to an equation or at least find a decent upper bound to be used in an estimate I need later. The ...
2
votes
0answers
25 views

Repeated application of interesting function on tuples

This question was inspired by Thursday's CIMC. Suppose you have a function $$f_n: (\Bbb{Z}/n\Bbb{Z})^n\to(\Bbb{Z}/n\Bbb{Z})^n; (a_1,a_2,a_3,\dots,a_n)\mapsto (b_1,b_2,b_3,\dots,b_n)$$ defined as ...
2
votes
3answers
133 views

Prove that $ 2^n \not \equiv 1 \pmod{n} $ for any $n > 1$.

I have proved this in following way. Assume that $ 2^n \equiv 1 \pmod{n} $. that means $n\mid(2^n -1)$. but by proof by contradiction, for $n=3$ this does not hold and we can say $n \nmid (2^n-1) ...
1
vote
0answers
63 views

Does this system of simultaneous Pell equations have any non-trivial positive integer solutions?

Let $a,b,c$ be positive integers satisfying \begin{align} 2a^2-1 &= b^2, \\ 2a^2+1 &= 3c^2. \end{align} The trivial solution is $(a,b,c)=(1,1,1)$. Are there others?
3
votes
3answers
95 views

find the last two digits of $2^{250}$.

Suppose we want the last two digits of $3^{250}$, one can use the theorem $a^{\phi(n)}\cong 1(\mod n)$ whenever $(3,n)=1$. But instead, if i have $2^{250}$, how do i solve this problem, because here ...
0
votes
0answers
25 views

$Ax+By+Cz=D \text { has a solution iff } \gcd(\gcd(A,B),C)\mid D$

I read today that $Ax+By+Cz=D \text { has a solution iff } \gcd(\gcd(A,B),C\mid D$ but I can't find it again, I also can't find any Diophantine equations with 3 variables that doesn't have solutions ...
0
votes
1answer
41 views

An effcient method of solving a Diophantine equation with 3 variables $Ax+By+Cz=D$?

I'm trying to make an efficient algorithm to find one of the solutions and how many solutions there are to the equation $$Ax+By+Cz=D$$ where $A,B,C,D\in \mathbb Z$ and the range for $x,y,z\in \mathbb ...
1
vote
2answers
42 views

Maximum GCD of two polynomials

Consider $f(n) = \gcd(1 + 3 n + 3 n^2, 1 + n^3)$ I don't know why but $f(n)$ appears to be periodic. Also $f(n)$ appears to attain a maximum value of $7$ when $n = 5 + 7*k $ for any $k \in \Bbb{Z}$. ...
2
votes
2answers
59 views

Find all solutions of the equation $n^m=x^2+py^2$ which satisfy the following properties

Prove or disprove that, There always exists a solution of the equation, $$n^m=x^2+py^2$$ with odd $x$ and $y$ and for all $m\geq k$ for some positive integral $k$. Here $p$ is an odd prime and ...
5
votes
1answer
63 views

How to solve the following equation in $\mathbb{Z}_n$?

Given an $n\in\mathbb{N}$, $a\in \mathbb{Z}_n$ and $x,y\in\mathbb{Z}$, how do I approach to solving the following equation: $a^x \equiv a^y \mod n$ I think that from here I can deduce that: $x ...
0
votes
1answer
54 views

A minimum Value Sum [closed]

The minimum value of $\sqrt{x^4 - x^2 - 24x + 145} + \sqrt{x^4 - 23x^2 - 2x + 145}$ can be expressed in the form ($a\sqrt{b}$), where $a$ is an integer, $b$ and is not divisible by the square of any ...
1
vote
0answers
29 views

Generalization of a Diophantine Equation Problem

I've been working a lot with Pythagorean triples and sums of squares that are themselves squares, specifically interlocking sums (where one square is part of two or more sums). As part of my work I ...
0
votes
2answers
20 views

Congruence Class

I'm having a hard time with number theory, I'm being asked to determine congruence classes of inverses. I'm hoping someone could give me a step by step walkthrough of the process to solve one of ...
2
votes
0answers
36 views

$a^2+5b$ and $b^2+5a$ are perfect squares

What are all pairs of positive integers $(a,b)$ such that $a^2+5b$ and $b^2+5a$ are perfect squares? When $(a,b)=(4,4)$, both numberes are $4^2+5\cdot 4=36$, which is a perfect square. Suppose ...
1
vote
5answers
32 views

If $a, b, c ∈ \Bbb{N}$, then at least one of $a-b$, $a+c$, and $b-c$ is even

This one has been frustrating me for a while. I need to find out whether the statement is true or not true and prove it. I think it's probably true, because it came out to be for every real number ...
2
votes
1answer
21 views

Solution for congruence mod $p^2$

I've been having trouble with the following congruence, finding all primes $p$ for $$x^2 + 1 \equiv 0\ mod\ p^2$$ By the definition of quadratic reciprocity, I know that $-1$ is a quadratic residue ...
4
votes
3answers
174 views

Prove there are k consecutive non-squarefree integers

So, I've got a question for class that asks me to prove the existence of arbitrarily long runs of consecutive integers where $\mu(n)$ is zero. I've started the proof, but I need a bit of help midway ...
0
votes
0answers
17 views

Connections of results in Harmonic analysis in the theory of Transcendental Numbers

Note :This question is proposed 2 years ago in MO , I see it appropriate for stackexhange math, i posted it here as it's unsolved problem and has a connection with Transcendental Numbers , mayeb we ...
0
votes
2answers
25 views

Number theory question to establish a relation

Suppose we have $$p^2 + q^2 + r^2 +pq + qr + pr=3$$ so can we use only this relation to find $$\frac{p^2 +2q^2+r^2}{q^2}$$?
1
vote
3answers
63 views

Prove $-1$ and $1$ are the only units in $\mathbb{Z}$ [closed]

Prove $\mathbb Z^*=\{-1,1\}.$ I have a proof, which is posted as an answer below. I'm looking for an alternate proof.
1
vote
3answers
68 views

Some questions on basic number theory

I have a number of questions related to proofs based on basic properties in number theory. While I would post them as separate questions, I feel that they are similar enough in the method that ...
2
votes
3answers
49 views

Is modular arithmetic defined for all rational numbers (with denominators coprime to modulus)?

In the expression $\frac{1}{b}\pmod m$, where $(b,m)=1$, is $\frac{1}{b}$: a) a rational number (and so rational numbers are defined in modulo arithmetic using multiplicative inverses)? b) just ...
3
votes
1answer
35 views

Finding a lower bound to the probability that a number will be shown to be composite?

Given the following method to decide whether a number $m$ is prime or not: Choose a random number $1<a<m-1$, and check whether $a^{m-1} = 1 \mod m$. If its equal, return true, otherwise - ...
1
vote
0answers
29 views

Prove a property of the divisor function (Part 2)

Further to this MSE question, I would like to pose a follow-up inquiry: If $n \in \mathbb{N}$ and $(\sigma(n) - n) \mid (n - 1)$, does it follow that $n$ and $\sigma(n)$ would have to be coprime, so ...
0
votes
1answer
27 views

Understanding Bézout's identity's proof as given on wikipedea.

I am reading this proof of Bézout's identity. It starts as: For given nonzero integers $a$ and $b$ there is a nonzero integer $ax + by$, $x$ and $y$ are also integers. The minimum absolute value of ...
1
vote
1answer
35 views

Primitive roots for a number

I want to show if a number a is a primitive root$\pmod{n}$ Is there a way to show this without raising a to all the powers between 1 and n-1?
0
votes
1answer
33 views

Proving $\lambda$ is the smallest one possible.

From this question , its proved that for all co-primes $a$ of $n(=pq)$ , $a^\lambda \equiv 1 \mod n$ where $\lambda= lcm (p-1,q-1)$ But how to prove that it is the smallest one possible . My ...
2
votes
2answers
26 views

How do I prove that for every positive integer $n$, there exist $n$ consecutive positive integers, each of which is composite?

I need help proving that for every positive integer $n$, there exist $n$ consecutive positive integers, each of which is composite. The hint that came with the problem is: Consider the numbers ...
0
votes
2answers
46 views

How do I find all the primes that are 1 less than a perfect cube?

I need some help with the problem in the topic (find all the primes that are 1 less than a perfect cube). So far I can see that if we let $a$ be some positive integer, then we are looking for all ...
4
votes
3answers
85 views

For what $a,b$ such that $ax^2+by^2 = z^2$?

This post made me think about this question. What is the criterion on positive integer $a,b$ such that, $$ax^2+by^2 = z^2$$ can be solved in positive integers $x,y,z$? (Three broad classes are: 1) ...
0
votes
2answers
26 views

Proving one-to-one and onto

So I am learning how to prove a function is one-to-one and onto. On some of the other threads in math stackexchange I noticed a proof: Assume f(m,n)=f(m',n'). To show from this that (m,n)=(m',n'). ...
2
votes
2answers
48 views

A question on divisibility

For what values of $x,y \in \{1,2,3,...9 \}$, does $$10x+y \space\mid 100x + y $$ ? What approach should I take for solving this problem ?
3
votes
2answers
34 views

What is $\gcd(x,x+2)$?

Show that $\gcd(x,x+2)$ is $1$ if $x$ is odd and $2$ if $x$ is even. I am looking for a much simpler proof beside the one which I have posted.
0
votes
1answer
14 views

In what case we get this relation: $a^{m}≡b^{m}(mod(c))$

Let $a,b$ and $c$ three natural numbers such that $a≡b \pmod{c}$. I am asking when getting relation $a^{m}≡b^{m}\pmod{c}$, in which $m \in \mathbb{N}$
2
votes
1answer
24 views

Reference for this theorem: $a, b$ coprime, $f(k) := ka \bmod b$, then $f$ is bijection on $\lbrace 0, …, b−1 \rbrace$.

I need to use the following theorem in a paper but have to expect that some of the audience (physicists) is not familiar with it, so I would like to reference it: Let $a$ and $b$ be two coprime ...
0
votes
0answers
19 views

Show that days with the identical calendar date in the years 1999 and 1915 fell on the same day of the week.

I think I'll be able to work this problem if I understand the quesiton. I am having difficulty in interpreting the problem(the phrase "identical calendar date" is throwing me off). Any help is ...
1
vote
1answer
38 views

$\lambda(n^2)$ versus $n\lambda(n)$

Let $\lambda$ be the Carmichael function. What is the relationship between $\lambda(n^2)$ and $n\lambda(n)$ ? It is easy to prove that $\lambda(n^2)\le n\lambda(n)$ $\ (\star)$. Actually, ...
1
vote
1answer
49 views

Maximum value of multiplicative order

Let $x \in \mathbb{Z}_{n^2}^*$ and let us assume that the multiplicative order of $x$ is multiple of $n$, then what is the maximum value of multiplicative order possible for $x$ under modulo $n^2$ ? ...
1
vote
2answers
46 views

Quadratic non-residues

While reading the book What is Mathematics? by Courant and Robbins, I've found a statement that I don't know how to prove, although it seems that it shouldn't be really difficult. Literally, they ...
3
votes
2answers
48 views

Prove that $4^{(p-1)/2}\equiv 1\pmod p$

If $p$ is a prime of the form $4k+3$, prove that $4^{\frac{p-1}{2}}\equiv 1\pmod p$. I was solving a problem and it came down to this. I have no idea how to prove it, I have tried. Any help would be ...
2
votes
3answers
68 views

Is this formula: $81n^2+135n+97$ wealth by prime numbers which n is natural number?

I made some effort to set a wealth quadratic formuala for prime, I found this formula: $A(n)= 81n^2+135n+97$, it gives primes for $n=0 $ to $n=18 $. I would be like some one to show me if this ...
1
vote
2answers
34 views

Coordinate where policeman catches thief if possible

A policemen and a thief are standing on x-axis with Policeman current position as (X1,0) and Thief is standing at (X2,0). Thief always runs away from Policeman . Policeman knows Thief is faster than ...
1
vote
1answer
55 views

Integer solutions to $a^4+b^7=11^{11}$

Determine the solution set of $a^4 + b^7 = 11^{11}$ with $a,b \in \mathbb{Z}$. Hints would be appreciated. I have tried working modulo $5$ and have deduced that $a$ or $b$ must be multiples of ...
4
votes
1answer
90 views

If $a,b > 1$ and $r>2$ does $ax^2+by^2=z^r$ have any rational solutions?

I have been trying to solve the following equation for months without much success. It has been so far a very frustrating endeavor.Please help. Consider the diophantine equation: $x^2+y^2=z^r$ where ...
3
votes
1answer
57 views

Find the range of values of $d$ for which the cubic equation $x^3-8x^2+12x+d=0$ has exactly $3$ distinct real roots

$$x^3-8x^2+12x+d=0 $$ I have worked this using calculus by finding the stationary points. However this is part of a problem which was under number theory. So I am still trying for a solution using ...
1
vote
1answer
29 views

Square and Multiply Decoding

Use the square and multiply method to decode the message 28717160 when $n=77$ and $d=13$. For the letter/number correspondence, use A=1. I have no idea what the "square and multiply method" is. I ...
3
votes
2answers
29 views

Even integer in ternary representation

Suppose $(d_0,d_1...d_k)_3$ is the ternary representation of a even integer $n$. Show that there is an even number values $d_0...d_k$ that are odd, whenever $n$ is even. I have tried decomposing ...
0
votes
3answers
35 views

Finding divisibility of a number using modular arithmetic

Let N = 12345678910111213141516171819. How can I use modular arithmetic to show that N is (or isn't) divisible by 11? In general, how can I apply modular arithmetic to determine the divisibility of an ...
11
votes
6answers
219 views

If the number $x$ is algebraic, then $x^2$ is also algebraic

Prove that if the number $x$ is algebraic, then $x^2$ is also algebraic. I understand that an algebraic number can be written as a polynomial that is equal to $0$. However, I'm baffled when showing ...