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

learn more… | top users | synonyms

1
vote
2answers
332 views

Is the notation for '$a$ divides $b$' standard?

I know that the notation $a | b$ means that there exists an integer $c$ such that $ac=b$, but is this notation completely standard and there's no way that it could be the other way round?
2
votes
2answers
3k views

Find all positive integers $n$ such that $\phi(n)=6$.

I am asked to find all positive integers $n$ such that $\phi(n)=6$, and to prove that I have found all solutions. The way I am tackling this is by constructing all combinations of prime powers such ...
0
votes
2answers
54 views

Jacobi symbol and invertibility of $m$ for an odd $n$

I have asked a similar question here before, and received a nice answer. I think that the next question here is equivalent, but can't seem to be able to prove it. Here goes: Given an odd $n$, I want ...
5
votes
1answer
379 views

Integer solutions of $x^4 + 16x^2y^2 + y^4 = z^2$

I come across this question very long ago. I just got one solution by my computer search. If any one know the other solutions and resolvability, please let me know. $$x^4 + 16x^2y^2 + y^4 = z^2$$ has ...
-1
votes
3answers
2k views

Efficient algorithms for computing Digits Sums Numbers

Is there any efficient way to generate these numbers? The sequence OEIS A038367: Numbers $n$ with property that (product of digits of $n$) is divisible by (sum of digits of $n$). First few: ...
2
votes
2answers
255 views

nature of diophantine solutions in general

I had a question in my mind from many years. we generally present the trivial solutions to Diophantine equations. Diophantine equations usually always have some sort of trivial solution (if you ...
0
votes
1answer
63 views

Is always $\small {rq-1 \over 2^B} \le q-1 $ with natural r,q,B and $\small r,q \in \{1, \ldots, (2^B-1)\} , odd$?

Consider the comparision in positive integers $$\small {rq-1 \over 2^B} \le q-1 $$ where $\small B $ is the given parameter and r and q are residues modulo $\small 2^B$ (which also implies, that the ...
10
votes
1answer
657 views

Finding pairs of triangular numbers whose sum and difference is triangular

The triangular numbers 15 and 21 have the property that both their sum and difference are triangular. There are another 4 pairs less than 1000. To complete this problem, I have done like this: To ...
0
votes
4answers
563 views

Divisibility properties

Let $a$, $b$, $c$ be integers. Prove that if $a|b$ and $a|(b+c)$ then $a|c$.
1
vote
0answers
114 views

How many ways to fill the $N \times N$ board by nonnegative integers, such that sum of the numbers of each row and each column is $R$?

How many ways to fill the $4 \times 4$ board by nonnegative integers, such that sum of the numbers of each row and each column is $3$? I wrote a brute-force and got $2008$ which seems to be the ...
2
votes
1answer
644 views

When is $a$ not a cube mod $p$

I would like to know when an integer $a$ is not a cube mod $p$. I already proved that if $p \equiv -1$ mod 3, then any integer is a cube mod $p$, but in the case where $p \equiv 1$ mod 3, I cannot ...
1
vote
1answer
74 views

Greatest $n$ that can be written in the form of $ax+by=n$

In a diophantine equation $ax + by = n$ with $(a, b) = 1$, the greatest possible value of $n$ such that both $(x, y)$ are not positive is $ab − b − a$? This is given in my module (without any proof). ...
4
votes
2answers
1k views

Order of an Element Modulo $n$ Divides $\phi(n)$

How can I show that the order of an element modulo $n$ divides $\phi(n)$? I know that if $a$ and $n$ are relatively prime, then the least positive integer $x$ such that $a^x\equiv1\pmod n$ is its ...
2
votes
1answer
90 views

showing that the Diophantine $3x^2+2=y^2+6z^3$ equation has no solutions

I'd really love your help with showing that the Diophantine $3x^2+2=y^2+6z^3$ equation has no solutions. I know that Diophantine equation of the form $ax+by+cz=d$ iff $\gcd(a,b,c) | d$, but how do I ...
5
votes
4answers
454 views

Show that $2^n$ is not a sum of consecutive positive integers [duplicate]

Possible Duplicate: A proof that powers of two cannot be expressed as the sum of multiple consecutive positive integers that uses binary representations? Suppose we have an arithmetic ...
0
votes
1answer
371 views

Contiguous prime numbers with MPI (Want more ideas for an efficient algorithm)

I am a programmer. I am working with Message Passing Interface (MPI) in C. I do a program that consist on finding the contiguous prime from 1 to 10,000,000. I already do it! but I do it with trial ...
2
votes
5answers
2k views

Prove that one of $n$ consecutive integers must be divisible by $n$

If we have $n$ consecutive integers, then one of these integers is divisible by $n$. Prove the above statement.
0
votes
2answers
161 views

Calculate constant using minimum number of operations on single digit constants

I have a machine that supports the arithmetic operations plus, minus (unary and binary), multiply, divide and exponent and can load single digit integer constants. Arithmetic operations are performed ...
2
votes
3answers
198 views

Solving $217 x \equiv 1 \quad \text{(mod 221)}$

I am given the problem: Find an integer $x$ between $0$ and $221$ such that $$217 x \equiv 1 \quad \text{(mod 221)}$$ How do I solve this? Unfortunately I am lost.
-4
votes
2answers
346 views

Sufficient condition for simple primality criterion?

There is a well known Giuga's Conjecture on Primality that states : $p~$ is a prime iff $~\displaystyle \sum_{i=1}^{p-1} i^{p-1} \equiv -1 \pmod p$ If we define $r_i$ as non-negative integer ...
1
vote
2answers
99 views

System of 3 Congruences

Trying to solve this system of congruences: $$n \equiv 4 \quad \text{(mod 19)}$$ $$n \equiv 3 \quad \text{(mod 10)}$$ $$n \equiv 6 \quad \text{(mod 11)}$$ how do I solve this?
4
votes
3answers
934 views

Is integer division uniquely defined in mathematics?

I am currently studying java programming and am a bit shaken up by the concept of integer division. I guess it is just a matter of getting used to that $1/2=0$, but I am afraid it might take some ...
2
votes
1answer
134 views

Congruence Summation Notation

I am given this problem: Suppose that a positive integer $n$, written in decimal notation, has digits (from left to right) $a_k, a_{k-1}, \ldots, a_0$. So $n = a_k 10^k + a_{k-1} 10^{k-1} + \cdots + ...
3
votes
1answer
232 views

Divisor/multiple game

Two players $A$ and $B$ play the following game: Start with the set $S$ of the first 25 natural numbers: $S=\{1,2,\ldots,25\}$. Player $A$ first picks an even number $x_0$ and removes it from $S$: ...
-3
votes
3answers
2k views

Product of consecutive even numbers

Prove that the product of three consecutive even numbers is a multiple of 8? show This into as much detail as possible!
8
votes
1answer
148 views

Pretty solution to question about floor function

I was recently asked this question by a student, and I don't know a nice, elegant way to solve it (actually, I'm not sure I know how to solve it at all). Let $S(\alpha)=\lbrace \lfloor ...
11
votes
1answer
113 views

Combinatorial question about sets of rational numbers

The following question came up in my research. Since lots of clever people post here, I thought I'd ask it. Recall that the group ring of a group $G$ is the abelian group $\mathbb{Z}[G]$ consisting ...
6
votes
3answers
252 views

Connections/motivations of “Sums of Two Squares” to/from other fields of math.

I am to teach section 18 of "Elementary Number Theory" (Dudley) - Sums of Two Squares - to an undergraduate Number Theory class, and am having trouble cultivating anything other than a rote dissection ...
1
vote
4answers
177 views

$2^x + 2^y = 129$: how to find the $x$ and $y$?

Sorry for my math language and the question header; I'm not capable of the terms used for the mathematics to ask the question via text; so I had to use the example above; feel free to edit if you can ...
6
votes
3answers
522 views

What is the largest positive $n$ for which $n^3+100$ is divisible by $n+10$

What is the largest positive $n$ for which $n^3+100$ is divisible by $n+10$ I tried to factorize $n^3+100$, but $100$ is not a perfect cube. I wish it were $1000$.
6
votes
1answer
73 views

Prove $1^a+2^a+\cdots+n^a < \frac{(n+1)^{(a+1)}-1}{a+1} $ for any $a >0$ and $n \in \mathbb{Z^+}$

Prove for any $a >0$ and $n \in \mathbb{Z^+} $ $$1^a+2^a+\cdots+n^a < \frac{(n+1)^{(a+1)}-1}{a+1}$$ Also for $a \in (-1,0)$ the above inequality is reversed. For $n=1, 2^{(a+1)}-1 > ...
1
vote
5answers
3k views

Proof of Extended Euclidean Algorithm?

There exist x and y such that: gcd (a,b) = xa + yb Why is this true? What's the reasoning behind it?
0
votes
4answers
241 views

Fermat's little theorem

Obtain residue class of $7^{9999}$ modulo 100 using the Little Fermat theorem. But I have no idea how to proceed.
4
votes
4answers
342 views

Number of quadratic residues mod $p$

I saw in a comment to this question that there are exactly $\frac{p-1}{2}$ quadratic redidues in $\mathbb{F}_p$, but I cannot find the proof by myself (it's been ages since I last touched this kind of ...
4
votes
0answers
234 views

Divisibility notation history

I'm writing a paper project for school about divisibility, so I'd like to include a bit of history about that subject. I'm mostly interested in notation of $|$ sign used in past, but everything else ...
0
votes
1answer
88 views

Prime factors of special numbers

Consider a positive odd integer $N>1$ of form $N=T^2+27U^2, T,U\in\mathbb{Z}, T, U\neq 0$ which cannot be divided by 3. Question: Suppose N can be divided by a prime number $p$, $p\equiv1(mod ...
0
votes
3answers
389 views

Legendre Symbol, Jacobi Symbol, and Quadratic Residues..

I am looking at this problem and I am confused on how one could easily compute this. Is it just the intersection of either non-quadratic residue or quadratic residues of the respective p and q?
1
vote
2answers
130 views

Constructive proof need to know the solutions of the equations

Observe the following equations: $2x^2 + 1 = 3^n$ has two solutions $(1, 1) ~\text{and}~ (2, 2)$ $x^2 + 1 = 2 \cdot 5^n$ has two solutions $(3, 1) ~\text{and}~ (7, 2)$ $7x^2 + 11= 2 \cdot 3^n$ has ...
0
votes
2answers
447 views

Cracking a Simple RSA Encryption

Show that if the encryption exponent $3$ is used for the RSA cryptosystem by three different people with different moduli, a plaintext message $P$ encrypted using each of their keys can be ...
1
vote
0answers
113 views

Generalizing a result on sums involving Euler's function

Motivation: It's known that there is a constant $0<K$ such that for any natural number $N$, $KN\leq \frac{\varphi(1)}{1}+\frac{\varphi(2)}{2}+\cdots+\frac{\varphi(N)}{N}$ (with $\varphi$ being ...
4
votes
2answers
483 views

Primes modulo which a given quadratic equation has roots

Given a quadratic polynomial $ax^2 + bx + c$, with $a$, $b$ and $c$ being integers, is there a characterization of all primes $p$ for which the equation $$ax^2 + bx + c \equiv 0 \pmod p$$ has ...
2
votes
0answers
81 views

Interesting Characteristic About the RSA Cryptosystem

I know that decryption in the RSA cryptosystem works because$$D\left(C\right)\equiv C^d\equiv \left(P^e\right)^d\equiv P^{ed}\equiv P^{k\phi\left(n\right)+1}\equiv ...
4
votes
4answers
4k views

Finding inverse of polynomial in a field

I'm having trouble with the procedure to find an inverse of a polynomial in a field. For example, take: In $\frac{\mathbb{Z}_3[x]}{m(x)}$, where $m(x) = x^3 + 2x +1$, find the inverse of $x^2 + ...
0
votes
1answer
100 views

Number of divisions using trial division to factorize the product of two k-digit primes

I'm more of a programmer than a Mathematician so please bear with me if my question is too trivial. I am looking up RSA specifically the key generation bit. Using Trial division, I know that it would ...
2
votes
1answer
168 views

Find the largest divisor of $1001001001$ that does not exceed $10000$.

Find the largest divisor of $1001001001$ that does not exceed $10000$.
2
votes
1answer
90 views

What is the probability that a multiple of $864$ is divisible by $1944$

If a positive integer multiple of $864$ is chosen randomly, with each multiple having the same probability of being chosen, what is the probability that it is divisible by $1944$?
6
votes
3answers
213 views

Number Theory and Probability Question

Compute the probability that a randomly chosen positive divisor of $10^{99}$ is an integer multiple of $10^{88}$
2
votes
2answers
233 views

Triplets based equation

Let $p \ge 7$ be a prime number. Find the triples $(x, y, z)$ in $\mathbb{Z}$ such as $xyz$ is not equal to zero, $\gcd (x, y, z) = 1$ and $x^p + 2y^p = z^2$. I want triplets and proof/generalization. ...
3
votes
4answers
639 views

Let $p$ be a prime. Prove that $p$ divides $ab^p−ba^p$ for all integers $a$ and $b$.

Let $p$ be a prime. Prove that $p$ divides $ab^p−ba^p$ for all integers $a$ and $b$. (This is not a homework)
0
votes
0answers
146 views

Infinitely many primes in every row of array?

Friend of mine gave me this problem : Consider the following array of natural numbers : $\begin{array}{ccccccccc} 1 & 2 & 4 & 7 & 11 & 16 & 22 & 29 & \ldots \\ 3 ...