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

learn more… | top users | synonyms (1)

1
vote
0answers
37 views

Special Case of Composite mersenne number mod p

We want to investigate if a composite mersenne number $2^{qb}-1\equiv0(mod\ p)$ where $q,p$ are primes, $p=1+6qb,\ qb\equiv1(mod8) $ and $b$ is an odd number. In general for $$\begin{align*} ...
0
votes
0answers
28 views

Looking for problems which can be solved by the similar technique

While browsing on internet for different proofs of Fermat's theorem on sums of two squares, I came across Zagier's "one-sentence proof" which seems to be the most elegant and short proof. It invokes a ...
0
votes
3answers
67 views

Calculate the exact value of the following expression [closed]

I propose the following exercise. Calculate the exact value of$$P=\dfrac{(10^{4}+324)(22^{4}+324)(34^{4}+324)(46^{4}+324)(58^{4}+324)}{(4^{4}+324)(16^{4}+324)(28^{4}+324)(40^{4}+324)(52^{4}+324)}$$ ...
5
votes
0answers
53 views

a new(?) operation using products of multiplicities

Does the operation $$n \odot m := \prod_{p \text{ prime}} p^{v_p(n) \cdot v_p(m)}$$ on positive integers have a common name? Has this operation been studied somewhere? Notice that $\odot$ is ...
2
votes
2answers
70 views

How can I simplify $123^{11} \mod 323$?

I am busy studying the RSA cryptosystem and would like to know how to simplify things like this: $123^{11} \mod 323$
4
votes
1answer
75 views

Does Euler's $\phi$ function have the same value in arbitrarily large subsets of $\mathbb{N}$?

As my most recent question still does not have any answers and it appears to be a difficult problem, I propose the following problem (that seems easier), but which I still could not manage to solve: ...
0
votes
3answers
25 views

Is there a simple way to simplify the congruence?

Is there a simple way to simplify the congruence? $25^{1203} \equiv 25^3 \pmod{23}$ without subtracting $23$ from $25^3$ a couple of times? In other words, I would like to rewrite it as: $25^{1203} ...
3
votes
1answer
17 views

How can I solve the linear congruence for x with the use of an inverse?

Consider, for example, the linear congruence: $56x \equiv 23 ($mod $93)$ if we know that the inverse of of $56$ modulo $93$ is $5$. Multiplying both sides by the inverse, $5$, we have: $280 x \equiv ...
0
votes
1answer
51 views

Use Fermat's little theorem to solve $7^{222}$mod $11$

The textbook gives the answer as: By Fermat’s little theorem, we know that $7^{10} ≡ 1 \pmod{11}$, and so $(7^{10})^k ≡ 1 \pmod{11}$, for every positive integer $k$. Therefore, $7^{222} = ...
1
vote
2answers
34 views

Comparison of two collections of 4-tuples using combinatorics - more complicated version

My problem is to show that 2 collections of unordered 4-tuples - $\mathbf{A}$ and $\mathbf{B}$ - are the same. I define a collection of objects as a set, in which multiple entries of the same object ...
1
vote
5answers
84 views

If $n = 4k + 1$, does $4$ divide $n^2 -1$?

How would I show that $4$ divides $n^2 -1$ if $n = 4k+1$? Is there more than one way to solve this?
-3
votes
1answer
47 views

Adding fractions in two ways - a paradox? [duplicate]

Adding 1/3 to 2/3 gives 1 EXACTLY. But expanding the two fractions and then adding gives 0.99999 Where is the flaw in this reasoning?
1
vote
2answers
55 views

Fourth power and least common multiple (urgent)

I have been given a mathematics test with the question* (we are allowed to use online resources): Find all positive answers for the following expression $$ x - y^4 = \def\LCM{{\rm lcm}}\LCM(x, y)$$ ...
1
vote
0answers
33 views

What are modulos and how would I be able to use them to solve questions regarding the last digit of a raised power?

When given questions like "What is the last digit of the result to 3^56?", I usually look for a recurring pattern involving smaller powers of 3. In this question for example, the recurring pattern for ...
3
votes
0answers
55 views

Is the set of integers so that $n!+1$ divides $(2012n)!$ finite or infinite?

I am having trouble with this problem. We have to determine whether the set of integers such that $n!+1$ divides $(2012n)!$ is finite or infinite. Basically we have to determine if the prime factors ...
2
votes
2answers
155 views

Divisibility question

Prove: (A) sum of two squares of two odd integers cannot be a perfect square (B) the product of four consecutive integers is $1$ less than a perfect square For (A) I let the two odd integers ...
1
vote
3answers
54 views

Find the number $ccbb$

If the number has $4$ digit $ccbb$ and it's full square, then find that number. I have tried and I got $88^2=7744$ but my way has no prove for it, if any one have away, I'll appreciate it.
-3
votes
3answers
65 views

Find the value of $x$ [closed]

Find the value of $x$, $$\left ( \frac{4}{\sqrt{3}-\sqrt{2}} \right )^{4-x}=\left ( 80+32\sqrt{6} \right )^{x}$$ any help?
2
votes
1answer
30 views

System of Congruences with Special Symmetry

Show that the following system of congruences \begin{align} \begin{cases} 3 x^4 - 7 x^2 y^2 - 7 x^2 z^2 - 35 y^2 z^2 \equiv 0 \pmod{p} \\ 3 y^4 - 7 x^2 y^2 - 7 y^2 z^2 - 35 x^2 z^2 \equiv 0 \pmod{p} ...
0
votes
3answers
151 views

Is infinity an element of the natural numbers? [duplicate]

I am wondering, whether $\infty \in \mathbb{N}$.
6
votes
2answers
301 views

Smallest Positive Integer Not Coprime to a Collection of Consecutive Integers

Let $n\in\mathbb{N}$. Define $f(n)$ to be the smallest positive integer $m$ such that there exists a positive integer $k$ for which $k+i$ is not relatively prime to $m$ for every ...
1
vote
2answers
38 views

Proving basic floor function inequality: $-1 \lt \lfloor 2x \rfloor - 2 \lfloor x \rfloor \lt 2$

As a direct consequence of the definition of $\lfloor x \rfloor $ I know that $$2x-1 \lt \lfloor 2x \rfloor \le 2x$$ and $$2x-2 \lt 2\lfloor x\rfloor \le 2x$$ How can I use these to show that $-1 \lt ...
1
vote
4answers
96 views

Find the value of $\frac{x}{y+z}+\frac{y}{z+x}+\frac{z}{x+y}$

If $$x+y+z=7$$ and $$\frac{1}{x+y}+\frac{1}{y+z}+\frac{1}{z+x}=\frac{7}{10}$$ Find the value of $$\frac{x}{y+z}+\frac{y}{z+x}+\frac{z}{x+y}$$ I tried but I got nothing
7
votes
0answers
127 views

Is the Euler function $\phi$ constant in arbitrarily large intervals?

Is it true that for every $k \in \mathbb{N}$ there exists a natural number $x$ such that $\phi(x)=\phi(x+1)=\cdots=\phi(x+k)$, where $\phi$ is the Euler's totient function? I thought about this ...
0
votes
1answer
35 views

Simple Linear Diophantine Equation - problem with proof.

I'm reading up on diophantine equations and one of the theorems is that "if $x,y$ is any solution of $ax + by = c$, then it is of the form $x_0 +\dfrac{b}{d}t ,\, y_0 - \dfrac{a}{d}t$ where $d = ...
1
vote
2answers
20 views

Distribution of decimal repunit primes

The prime number theorem describes the distribution of prime numbers in positive integers. Is there a similar theorem describing the distribution of primes among positive integers of the form ...
5
votes
2answers
69 views

Can $|m\alpha+n\beta|$ be made arbitrarily small?

I wondered is that always true that if $\alpha$ and $\beta$ are non-zero real numbers, then can we make $|m\alpha+n\beta|$ arbitrarily close to zero, for some non-zero integers $m$ and $n$. My guess ...
1
vote
5answers
49 views

Divisibility theory help

If $a$ is odd, show that $32 \mid (a^2 + 3)(a^2 + 7)$ Since $a$ is odd, I let $a = 2b + 1$ and did the expansion to get $16\mid [(b^2 + b +1)(b^2 + b + 2)]$, but I was unable to continue from ...
2
votes
1answer
43 views

How do you calculate variables as exponents in a polynomial without a calculator?

Good day The problem is as follow: Find all solutions $(x, y)$, where $x, y \in \mathbb {Z^+}$ to the equation: $$1+3^x=2^y$$ Two solutions are $(0,1)$ and $(1,2)$ but how do you go about ...
0
votes
1answer
41 views

Roots of polynomials $\pmod {p^2}$

Let $f(x)=x^l+x^{l-1}+x^{l-2}+\cdots+x^2+x+1$, $p$ being prime, $f(x)\equiv 0\pmod {p^2}$ if $p\equiv 1\pmod l$ or $p=l$ has $l$ roots, otherwise it has none. So what can be said about ...
1
vote
1answer
34 views

Define recursively the sequence of the cubes of natural numbers

Let $n $ be an element of the natural numbers, and let $s(n) $ be the series defined by the squares of the natural numbers, i.e. $s(n) =0, 1, 4, 9, 16, 25, 36,... $ I have worked out the recursive ...
3
votes
1answer
64 views

Frazzle game question

In $7^{th}$ grade, in order to learn divisibility, memory, and focus, my math teacher had my pre-algebra class play a game called Frazzle. To play the game Frazzle, each person went around the room ...
-2
votes
1answer
76 views

Can anyone Find the error below [duplicate]

If: $$S=1+2+4+8+....+2^n +...$$ So we get $$2S=2+4+8+...$$ $$2S+1=1+2+4+8+16...$$ $$2S+1=S$$ $$2S-S=-1$$ $$S=-1$$ Is there error, and if there's, why? I want athletic explanation.
0
votes
1answer
47 views

Show that a prime p divides $a^p - a$. [duplicate]

Let $p$ be a prime. I want to show that $p | a^p - a$. I want to use induction. I showed that this is true for the case $a = 1$. I'm having trouble with the bridge.
0
votes
2answers
54 views

Find integer solution of sysem of quadratic equations [closed]

If: $a,b,c$ positive integers, where $a\geq b\geq c$. such that: $$a^2 - b^2 - c^2 +ab=2011$$ $$a^2 +3b^2 +3c^2 -3ab-2ac-2bc=-1997.$$ Find the value of $a$ I tried, but I got nothing. Source: 2012 ...
-1
votes
2answers
62 views

Highest power of a prime in the product of consecutive factorials [closed]

$y$ and $n$ are positive integers. $1!\times2!\times3!\times...\times26! = y\times13^n$ $n$ is equals ? ($n$ is above)
0
votes
2answers
41 views

Comparison of two sets of 4-tuples using combinatorics

My problem is to show that $\mathbf{A} = \mathbf{B}$. Specifically that $\forall a \in \mathbf{A} \implies a \in \mathbf{B}$ and $\forall b \in \mathbf{B} \implies b \in \mathbf{A}$, to be precise. ...
2
votes
2answers
65 views

Prove that $2^{9693}-1$ divisible by $7$

Prove that $2^{9693}-1$ divisible by $7$, by more than one way. my try... that, the power divisible by $3$ so it's divisible by $7$ like $2^3,2^6,2^{12}$ and I think it's wrong.
0
votes
1answer
52 views

Please help me understand this modular arithmetic.

We have this question on a review sheet in my discrete math class and I have also provided the given answer. I am totally lost when it comes to this stuff, and I would just like an explanation of why ...
3
votes
2answers
50 views

Three variable, second degree diophantine equation

I am trying to solve this diophantine equation: $x^2 + yx + y^2 = z^2$ In other words, I am trying to find integers $x$ and $y$ such that $x^2 + yx + y^2$ is a perfect square. So far, the only ...
7
votes
1answer
99 views

Distribution of the sum reciprocal of primes $\le 1$

$$\frac{1}{2}+\frac{1}{3}+\frac{1}{7}+\frac{1}{43}+\cdots \le 1 $$ This is an interesting infinite summation. This is very closely resembling my other problem with has to do with the distribution of ...
0
votes
2answers
33 views

If $g$ is a primitive root modulo $p$, then $(p-1)! \equiv g^{p(p-1)/2} \pmod{p}$

Does anyone know how to prove the following theorem: If $g$ is a primitive root modulo $p$ (and $p$ is a prime number), then $$(p-1)! \equiv g^{p(p-1)/2} \pmod{p}.$$
2
votes
1answer
67 views

Calculation of product of all coprimes of number less than itself

Is there any fast way or formula to calculate product of all coprimes of a number less than itself? How can we do it without finding all coprimes manually? Note : I have to find actually (product) ...
2
votes
1answer
21 views

Prove zeta-esque relationship with floor function

I'm looking to show that: $$ \frac1{1-2^{-s}} \frac1{1-4^{-s}} = \sum_{k=0}^\infty \frac{\left\lfloor1+\frac{k}{2}\right\rfloor}{2^{ks}}$$ I've noticed $(1-4^{-s})^{-1} = (1-2^{-2s})^{-1}$ and I'm ...
7
votes
2answers
104 views

Does the sum of the reciprocals of composites that are $ \le $ 1

The sum itself: $$ \frac{1}{4}+\frac{1}{6}+\frac{1}{8}+\frac{1}{9}+\frac{1}{10}+\frac{1}{12}+\frac{1}{14}+ \frac{1}{15}+ \frac{1}{39}... \le 1 $$ These are all sums of reciprocals of composites that ...
1
vote
0answers
13 views

Adam isomorphism of circulant graphs

Let $C(n; S)$ denote a circulant graph on $n$ vertices (the vertices can be labeled $0,\ldots,n-1$), and connection set $S = \{s_1, \ldots, s_k \}$. Let $1 \leq \mu < n$ be relatively prime to $n$. ...
1
vote
0answers
17 views

A question on the representation of all integers in terms of the sum of other interger cubes [duplicate]

The question is from a book used for transition between high school mathematics and university mathematics, which states: Prove the following statement or give a counterexample $\forall n \in ...
2
votes
3answers
48 views

Find all numbers that have 30 factors and have 30 as one of their factors.

Find all numbers that have 30 factors and have 30 as one of their factors. Thank you. Note: please show way if possible.
0
votes
1answer
31 views

The solutions to $x^m \equiv 1 \bmod p$ will all be solutions to $x^{mn} \equiv 1 \bmod p$ for any $n$.

Can you please show the proof of "The solutions to $x^m \equiv 1 \bmod p$ will all be solutions to $x^{mn} \equiv 1 \bmod p$ for any $n$."
0
votes
0answers
31 views

Solve $x^n\equiv1 \pmod p$ for $x$ where $n$ is odd, $p$ prime [duplicate]

The solution to $x^3\equiv1 \pmod p$ has been discussed in Solve $x^3 \equiv 1 \pmod p$ for $x$ and explained elegantly by Arturo Magidin. The discussion established the form of $p$ and $x$. What ...