Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.
-1
votes
2answers
126 views
How to fast check if a number is a prime number? [closed]
Let say I've found a very very very long prime number. I know it's prime but I need to have a proof. Is there any fast way how to check if a number is really prime?
Let say I've found the longest ...
1
vote
4answers
85 views
Finding the last digit in a large exponent.
I'm practicing for my algebra exam but I stumbled on a question I don't know how to solve.
Let N = 3^729. What is the last digit of N?
The example answer says Since gcd(3, 10) = 1, check that
3^4 = ...
1
vote
2answers
52 views
how to show that a function$f$ is contained in all natural numbers?
Let $f:\mathbb{N}\times\mathbb{N}\rightarrow \mathbb{R}$ be defined by $f(a, b) = \frac{(a+1)(a+2b)}{2}$.
Carefully show that the image of $f$ is contained in $\mathbb{N}$.
1
vote
1answer
48 views
Congruence modulo a prime.
The goal is to show that $x^2+3\equiv 0 \pmod p$ is solvable for every prime $p$, $p\equiv 1 \pmod 3$.
What I know so far is that, since $3\mid (p-1)$, $x^3\equiv 1 \pmod p$ has exactly three ...
2
votes
1answer
33 views
Formula/Algorithn for Exponential factoring?
Given $s = a^b$ find $a$ and $b$. my first algorithm was the obvious brute force method of checking all $b$ roots or dividing by all possible $a$. But I am wondering if there is a more efficient ...
10
votes
1answer
85 views
Proving existence of a square-free sequence
I found this problem and a solution sketch in a MathOverflow answer, and I thought it was nice enough to deserve more attention and a properly written solution.
Problem:
Prove that for each ...
3
votes
1answer
103 views
Is my proof correct? $p_1p_2p_3\cdots p_n+1)$ cannot be the square of an integer
Prove that $p_1p_2p_3\cdots p_n+1$, where $p_n$ is the $n^{th}$ prime, cannot be the square of an integer.
Let $p_1p_2p_3\cdots p_n+1=Q$ and assume it is the square of an integer, so ...
2
votes
0answers
44 views
Euler product of $\frac{1}{\gamma}$
I am trying to calculate the euler product of $\frac{1}{\gamma}(n)$ where $\gamma(n)$ is the number of divisors of n. So I have that:
$\displaystyle D_{\frac{1}{\gamma}(n)}=\prod_p \left ( 1+ ...
4
votes
2answers
52 views
Maximal Smallest Number
Ran into a interesting problem which I have no idea how to solve but have the desire to.
Let a and b be two positive real numbers and let $m$(a,b) be the smallest of the three numbers $a,$ $1/b$ ...
2
votes
3answers
62 views
Congruences modulo a prime p
How would you go about showing that (for $a \in \mathbb{Z}$) $x^{2}+a^{2}$ divides $x^{p-1}-1$, modulo a prime $p$, where $p\equiv 1 \mod 4$?
My first thought was to use the fact that there exists a ...
0
votes
0answers
26 views
Proof of Lempel-Golomb construction of Costas array
Can anyone please help me to prove Lempel-Golomb construction of Costas array, i.e., ${g_1}^i + {g_2}^j = 1$ forms costas array where $g_1$ and $g_2$ are primitive roots of a prime $p$ and $1\leq i ...
4
votes
1answer
54 views
Given any power of 2, there exist infinitely many powers of 2 whose decimal representation ends with the digits of the given power of 2.
I have got a question that I am not able to understand how to solve it? .
Given any power of 2 (such as 1024), there exist infintely many powers of 2 whose decimal representation ends with the ...
2
votes
5answers
158 views
Find all solutions: $x^2 + 2y^2 = z^2$
I'm use to finding the solutions of linear Diophantine equations, but what are you suppose to do when you have quadratic terms? For example consider the following problem:
Find all solutions in ...
9
votes
1answer
237 views
Prove that all prime divisors of $7a^2(a+1)-1$ are of the form $7k\pm1$
Question:
Let a be a positive integer. Prove that all prime divisors of $7a^2(a+1)-1$ are of the form $7k\pm1$
$a$ and $k \in \mathbb{N}$ .
2
votes
3answers
62 views
Why does $\gcd(a, b) = \min\lbrace ma + nb : m, n\in\mathbb{Z}\text{ and }ma+nb>0\rbrace$?
$\gcd(a, b)$ should have the form of $ma+nb$, where $m,n\in\mathbb{Z}$, since $(a, b)$ divides both $a$ and $b$.
But I dont know why it should be the smallest one which is positive.
1
vote
0answers
69 views
On the elliptic curve $x^4+y^4 =193z^2$
Given the simultaneous Diophantine equations,
$$u^2+v^2=w^2\tag{1}$$
$$x^4+y^4 = (u^6+v^6)t^2\tag{2}$$
the only solutions seem to be for the first Pythagorean triple $u,v,w = 3,4,5$ which yield the ...
2
votes
1answer
31 views
$x + y \equiv x - y \equiv 1, 7 \space mod \space 8$?
I'm stuck on the following problem:
Let $x, y, z$ be primitive Pythagorean triples with $y$ even
Prove that $x + y \equiv x - y \equiv 1, 7 \space mod \space 8$
So far I've tried forming ...
4
votes
0answers
63 views
Determine the least prime $p$ for which $2^{p-1} \equiv 1 \pmod {p^2}$.
Determine the least prime $p$ for which $2^{p-1} \equiv 1 \pmod {p^{2}}$ .
2
votes
1answer
41 views
Find a divisor satisfying a given congruence
Suppose I have a highly composite positive integer $N$ with at least $10^{15}$ divisors for which I know the prime factorization.
Given $M$ with $\gcd(M,N)=1$ is there an efficient way to find a ...
2
votes
2answers
48 views
Solve the quadratic congrunce
Solve the following quadratic congreunce
$x^2+ 7x + 10 \equiv 0$ (mod $11$).
I want to know a general and easy method how to solve this kind of questions.
1
vote
3answers
84 views
$a^{37} \equiv a \pmod {1729}$ [duplicate]
Use Euler theorem to show that
$$a^{37} \equiv a \pmod {1729}$$ is true for any integer $a$.
I am a beginner in Number theory and stuck in this problem. Show me the right direction.
0
votes
0answers
23 views
Pell's d prime (often) implies that x(d-1) is prime?
I have found a few patterns in my study of Pell’s equation x(d)^2-dy(d)^2=1.
One is this: If d is a prime then x(d-1) is also prime.
It doesn’t hold for all primes, but it is a pattern which holds ...
3
votes
3answers
81 views
can't understand a simple divisibility probelm
I am reading this book. In the example 1.1 they said to prove this problem.
probelm
Let $x$ and $y$ be integers. Prove that $2x + 3y$ is divisible
by $17$ iff $9x + 5y$ is divisible by $17$
the ...
3
votes
2answers
48 views
solution set for congruence $x^2 \equiv 1 \mod m$
if $m$ is an integer greater than 2, and a primitive root modulo $m$ exists, prove that the only incongruent solutions of $x^2 \equiv 1 \mod m$ are $x \equiv \pm 1 \mod m$.
I know that if a primitive ...
3
votes
1answer
113 views
Solving the general quadratic congruence mod $2^k$
Under what conditions on $a,b,c,k$, is there a solution to $$ax^2+bx+c\equiv 0 \pmod{2^k}?$$
Related things that I believe to be true:
If $2$ were instead an odd prime, a solution exists precisely ...
2
votes
1answer
63 views
A game involving points in the integer plane - who wins?
I am running a workshop on puzzles and problem solving over the weekend and thought that it might be a good idea to get people engaged by phrasing some interesting mathematical results in terms of ...
1
vote
3answers
75 views
Express Integer as Sum of Four Squares
This is kind of a follow-up to the question I posted here about expressing integers as the sum of two squares. Is there a similar general method for expressing integers as the sum of four squares? I ...
2
votes
2answers
49 views
About linear combinations of primes
$a,b,c$ are natural numbers whose greatest common divisor is $1$.
$a,b,c\in\mathbb{N}^*$, $(a,b,c)=1$
Try to write down the expression using $a,b,c$ of the biggest natural number $M$ that cannot be ...
3
votes
4answers
69 views
Greatest Common Divisor
I have calculated $d = 39$ but don't know how to find $u$ and $v$.
Btw I know this is not really a cryptography question, but there isn't a tag for GCD.
3
votes
1answer
76 views
Express Integer as Sum of Two Squares
Is there a general method to expressing integers as the sum of two squares or do you just need to be good with numbers? For example, consider the following problem:
Express 605 as the sum of two ...
3
votes
2answers
115 views
Find all the natural numbers where $ϕ(n)=110$ (Euler's totient function)
Find all the natural numbers where $ϕ(n)=110$ (Euler's totient function)
What the idea behind this kind of questions?
3
votes
1answer
77 views
Using Fermats Little Theorem to show $2^{17} -1$ is prime
Show that $n = 2^{17} - 1$ is prime by using Fermat's Little Theorem $2^{p-1} \equiv 1 \mod p$ for any $p$ dividing $n$.
I said, that by FLT, we get $2^{16} \equiv 1 \mod 17$, and we can see that ...
0
votes
1answer
25 views
Linear diophantine equation solution existence
Given the linear diophantine equation
$$ax+by=c $$
I have to show that it has solution if and only if $gcd(a,b)$ divides $c$.
$$1)\Rightarrow $$
Let $m=gcd(a,b)$ then
$$a'x+b'y=c'$$
where ...
0
votes
1answer
35 views
Ghandhan statement on Characteristic of Fifth power of number $(n \cdot n \cdot n \cdot n \cdot n)$
I have identified few unique characteristics of fifth power of a number i.e. $n \cdot n \cdot n \cdot n \cdot n$.
Below are the 2 Characteristics.
For any integer number N,
Last digit of $N$ and ...
6
votes
0answers
126 views
How prove this arithmetic progression cannot have terms of the form $2^m+3^n$ only?
Let $a_{i}\in \mathbb{N}$, $a_{i}\ge 1$, $i=1,2,\ldots,7$ be arbitrary, and such that
$a_{n+1}-a_{n}=d\neq 0,n=1,2,\cdots,6 $.
Then there exists $a_{\ell}$, $\ell=1,2,\ldots,7$, such that
...
4
votes
4answers
143 views
Is every prime number the leg of exactly one right triangle with integer sides? What's wrong with my argument that this is impossible?
The problem is: "prove that every prime number is the leg of exactly one right triangle with integer sides." However, I seem to have proved that this is impossible. What did I do wrong here?
Let ...
3
votes
4answers
83 views
Formulae for both identifying or generating primes; Shows arranged distribution. Solved; basically trial division.
While looking at numbers and considering $n < p < 2n - 2$ and $p = 3n\pm 1$, where $p$ is any prime number, I was able identify a property for numbers $c=3n\pm 1$ where $c$ is a composite ...
1
vote
1answer
31 views
Understanding Diophantine Equation Proof /w link
There is a proof that I'm trying to understand, but the textbook I have isn't making any sense and my teachers explanations are not very clear to non-existent. I'm trying to understand why:
$$x^4 - ...
0
votes
1answer
53 views
Number Theory Proof Need Logic Checked
I'm working on the following problem:
Show that if $x^{p} + y^{p} = z^{p}$, then $p \space | \space (x + y -z)$
So far my proof looks something like this:
Suppose $p \nmid \space (x+y-z)$ ...
1
vote
0answers
35 views
Upper bound on degree of coefficients required to write polynomials as a linear combination of $f_1,…,f_n$
All polynomials will be elements of $\mathbb{Q}[x]$. Suppose $f_1,...,f_n$ are polynomials of degree at most $d$ which are coprime. What is a (hopefully sharp) upper bound on the degree of ...
1
vote
1answer
22 views
Diophantine Equation Proof with Prime Exponent?
How can you show that given a prime number p, if $x^{p-1} + y^{p-1} = z^{p-1}$ then $p \space | \space xyz$ ? I'm really looking for techniques to use because I have a couple more problems like this ...
2
votes
2answers
68 views
Given one primitive root, how do you find all the others?
For example: if $5$ is a primitive root of $p = 23$.
Since $p$ is a prime there are $\phi(p - 1)$ primitive roots. Is this correct?
If so, $\phi(p - 1) = \phi(22) = \phi(2) \phi(11) = 10$. So ...
1
vote
5answers
56 views
Infinite number of solutions (Diophantine Equation)
I’m not sure how to approach this number theory problem I’ve been working on for a while. So basically I need to show that the Diophantine equation
$$x^2 + y^2 = z^3$$
has an infinite number of ...
5
votes
2answers
134 views
Pythagorean triples and perfect squares
This problem is giving me difficulty:
Show that in any Pythagorean triple there exist at most a single perfect square
So far I've been working with the equations for primitive Pythagorean ...
2
votes
1answer
44 views
Diophantine Equations (Reciprocals?)
I'm having difficulty solving the following problem:
Consider the following Diophantine equation
$$\frac{1}{x^4} + \frac{1}{y^4} = \frac{1}{z^2}$$
Show that this equation has no ...
4
votes
2answers
94 views
how to prove $\frac {(a_1+…+a_k-1)!}{a_1!…a_k!} \in \Bbb N$
if $a_1,...,a_k \in \Bbb N$ , $\gcd(a_1,...,a_k)=1$ how to prove:
$$\frac {(a_1+...+a_k-1)!}{a_1!...a_k!} \in \Bbb N$$
Thanks in advance.
5
votes
1answer
130 views
Does there exist a positive integer $n$ such that it will be twice of $n$ when its digits are reversed?
Does there exist a positive integer $n$ such that it will be twice of $n$ when its digits are reversed?
We define $f(n)=m$ where the digits of $m$ and $n$ are reverse.
Such as ...
2
votes
3answers
70 views
How to find the last two digit of $7^{81}$? [duplicate]
Could any one tell me how to find the last two digit of $7^{81}$? I have succeeded in finding the last digit only which is $7$.
Any group theoretic approach or any other approach is welcome.
1
vote
1answer
50 views
An exercise in Number theory
Let $m$, $n$ and $k$ be positive integers with gcd$(mn, k) = 1$. How can I prove that $x^m + y^n = z^k $has a solution in positive integers?
5
votes
2answers
53 views
How do I append an integer to the left of another integer?
For example:
. is my append operator
f(x,y) = |x| . |y|
f(1,45) = 145
f(233,10) = 23310
f(8,2) = 82
f(0,1) = 1
This is a trivially easy problem to ...
